回溯

2、4、5、7、8、9、10、11、13、14、15、16、

回溯就是：横向遍历(for循环)，纵向递归(for循环里面的回溯方法)的组合。

对于全排列，for循环从零开始遍历，并且使用used数组
为了防止出现重复的结果，使用startIndex （第一棵子树选了2、3，第二棵子树选了3，就不能再选2）

回溯法的代码框架：

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }
    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;   (eg:字符串新加入一个字符、设置该位置已读等等)
        backtracking(路径，选择列表);     // 递归
        回溯，撤销处理结果  (eg:去除之前新加入的字符、取消该位置的已读等等)
    }
}

回溯问题分类：

子集、组合（startIndex）

全排列（used数组）
全排列问题去重：
“树间横向去重”：
1. 47. 全排列 II (树层去重+树枝去除已使用)
```
//存在重复数字
Arrays.sort(nums);
if(used[i] || (i>0&&nums[i]==nums[i-1]&&used[i-1]==false)){
    continue;
}
```
“子树纵向去重”：
1. 46. 全排列（树枝去除已使用）
```
if(used[i] == true)
```
  如图，同一树枝上(backtrack())可以重复选，而同一父节点的相同层上(for循环)的不可以重复选取元素。
   // used[i] == true，说明同一树枝nums[i]使用过（同一树枝是在同一个backtrack方法里的）
   // used[i] == false，说明同一树层nums[i]使用过（同一树层是在不同拔backtrack方法里面的，或者说他前面的那条树枝的backtrack方法已经重置了状态才轮到现在这个树枝）

简单

中等

77. 组合
216. 组合总和 III
17. 电话号码的字母组合
39. 组合总和
131. 分割回文串
93. 复原 IP 地址
78. 子集
90. 子集 II
491. 非递减子序列（类似树层区中）
46. 全排列（树枝去除已使用）
47. 全排列 II (树层去重+树枝去除已使用)
113. 路径总和 II (二叉树的回溯，和列表的回溯一样，backtrack=终止条件+遍历backtrack)

链表

2、

简单

203. 移除链表元素

中等

2. 两数相加

双指针

1、2、4、5、6、7、8、9、10

简单

27. 移除元素

中等

151. 反转字符串中的单词

贪心算法（局部最优推导全局最优）

2、4、7、8、9、11、13、14、18、19、20

简单

455. 分发饼干

中等

53. 最大子数组和

困难

135. 分发糖果

动态规划（重叠子问题，状态推导）

tips：

题目让求“最大”，你就要准备好在dp数组初始化为Integer.MIN_VALUE，方便之后比较大小。

但是，很可能需要把dp[0]置为0.

Arrays.fill(dp,Integer.MIN_VALUE);
dp[0]=0;

动态规划，英文：Dynamic Programming，简称DP，如果某一问题有很多重叠子问题，使用动态规划是最有效的。

所以动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优的。

7、8、13、16、19、21、26、29、30、32、34、41、42、43、44、46、47、50、52、53

背包问题：

dp[i][j]：i代表物品，j代表背包容量，表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。有的题没有“价值”，或者说价值就是“种数”（求有多少种xx之类的）

0-1背包：每个物品只有一个。
- 递归公式： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
完全背包：每个物品可以有多个（取用多次）。
- 递推公式： dp[i][j] = max(dp[i - 1][j], dp[i][j - weight[i]] + value[i]);

0-1背包递推公式可以压缩为1维：
- dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]，那么dp[0]就应该是0，因为背包容量为0所背的物品的最大价值就是0。
- 递推公式：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
- 遍历顺序：物品遍历的for循环放在外层，遍历背包的for循环放在内层，且内层for循环倒序遍历！

遍历顺序：

如果求组合数就是外层for循环遍历物品，内层for遍历背包。

如果求排列数就是外层for遍历背包，内层for循环遍历物品。

递推方法：

这里我们dp[1][4]的状态来举例：

求取 dp[1][4] 有两种情况：

放物品1
还是不放物品1

如果不放物品1，那么背包的价值应该是 dp[0][4] 即容量为4的背包，只放物品0的情况。

如果放物品1，那么背包要先留出物品1的容量，目前容量是4，物品1 的容量（就是物品1的重量）为3，此时背包剩下容量为1。

容量为1，只考虑放物品0 的最大价值是 dp[0][1]，这个值我们之前就计算过。

初始化：

如果背包容量j为0的话，即dp[i][0]，无论是选取哪些物品，背包价值总和一定为0。

状态转移方程可以看出i 是由 i-1 推导出来，那么i为0的时候就一定要初始化。

dp[0][j]，即：i为0，存放编号0的物品的时候，各个容量的背包所能存放的最大价值。

那么很明显当 j < weight[0]的时候，dp[0][j] 应该是 0，因为背包容量比编号0的物品重量还小。

当j >= weight[0]时，dp[0][j] 应该是value[0]，因为背包容量放足够放编号0物品。

1、0/1背包：外循环nums,内循环target,target倒序且target>=nums[i];

2、完全背包：外循环nums,内循环target,target正序且target>=nums[i];

3、组合背包(考虑顺序)：外循环target,内循环nums,target正序且target>=nums[i];

4、分组背包：这个比较特殊，需要三重循环：外循环背包bags,内部两层循环根据题目的要求转化为1,2,3三种背包类型的模板

1、最值问题: dp[i] = max/min(dp[i], dp[i-nums]+1)或dp[i] = max/min(dp[i], dp[i-num]+nums);

2、存在问题(bool)：dp[i]=dp[i]||dp[i-num];

3、组合问题：dp[i]+=dp[i-num];

链接：https://leetcode.cn/problems/coin-change/solutions/778891/yi-pian-wen-zhang-chi-tou-bei-bao-wen-ti-sq9n/

背包问题中等

494. 目标和

416. 分割等和子集
518. 零钱兑换 II (求组合数，外层物品，内层背包)
377. 组合总和 Ⅳ (求排列数：外层遍历背包，内层遍历物品) （完全可以视为爬楼梯的问题）
322. 零钱兑换
139. 单词拆分（也可以想象成爬楼梯，能不能爬到第i阶台阶？当时看dp[i-len[j]]是不是true啦）
121. 买卖股票的最佳时机

简单

674. 最长连续递增序列

392. 判断子序列（我的写法是判断a和b字符串的最长公共子串是不是长度等于b）

中等

122. 买卖股票的最佳时机 II

300. 最长递增子序列
63. 不同路径 II
279. 完全平方数（也是上楼梯的变种，只不过步距没有明着写出来，这道题的步距是完全平方数，外层遍历楼梯，内层遍历步距）
343. 整数拆分 (思想类似279. 完全平方数 ,还是上楼梯，只不过是求乘积 )
198. 打家劫舍
213. 打家劫舍 II
718. 最长重复子数组
1143. 最长公共子序列
53. 最大子数组和
72. 编辑距离
647. 回文子串
516. 最长回文子序列

二分查找

二分查找的平均时间复杂度：O (log n)

lowerBound(): 查找第一个>=target的数的下标

private int lowerBound(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1; // 闭区间 [left, right]
    while (left <= right) { // 区间不为空
        // 循环不变量：
        // nums[left-1] < target
        // nums[right+1] >= target
        int mid = left + (right - left) / 2;
        if (nums[mid] >= target) {
            right = mid - 1; // 范围缩小到 [left, mid-1]
        } else {
            left = mid + 1; // 范围缩小到 [mid+1, right]
        }
    }
    // 循环结束后 left = right+1
    // 此时 nums[left-1] < target 而 nums[left] = nums[right+1] >= target
    // 所以 left 就是第一个 >= target 的元素下标
    return left;
}

由高亮部分代码，我们可知：

最终nums[r+1]一定>=target, 而nums[l-1]一定<target, 故而，最终应该return l，而l也是在这个非递减数组中第一个>=target的下标，因此方法名字叫做：lowerBound()

当数组中元素都<target时，将会返回nums.length