Leetcode-代码随想录总结

内容整理自代码随想录

1. DP 动态规划

1.1 思路框架

动规五部曲分别为：

确定dp数组（dp table）以及下标的含义

一般来说，dp数组元素即为题目所求的局部最优结果。分析问题规模确定数组维数；
确定递推公式

注意紧扣数组定义；
dp数组如何初始化
确定遍历顺序

根据递推公式所需的上下文，确定方向。

如有 dp[i][j] = dp[i + 1][j - 1] + 1，则遍历顺序为 i由大到小，j由小到大；
举例推导dp数组

辅助Debug检验代码实现/递推公式缺漏。

1.2 背包问题

思路

题目不会直给地点明是背包问题，需要分析物品和背包对应题目中的什么元素。有时元素同时是物品和背包。

01背包（每种物品仅有1件）

——滚动数组实现

dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]。

for(int i = 0; i < weight.size(); i++) { // 遍历物品
    for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

    }
}

倒序遍历是为了保证物品i只被放入一次！

完全背包（每种物品有无限件）

完全背包的物品是可以添加多次的，所以要从小到大去遍历，即：

// 先遍历物品，再遍历背包
for(int i = 0; i < weight.size(); i++) { // 遍历物品
    for(int j = weight[i]; j <= bagWeight ; j++) { // 遍历背包容量
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

    }
}

但是仅仅是纯完全背包的遍历顺序是这样的，题目稍有变化，两个for循环的先后顺序就不一样了。

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

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

1.3 其他系列

2. 回溯法

2.1 模板

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

2.2 要点

组合问题，收集叶子节点的结果
- 对于组合问题，什么时候需要startIndex呢？
  
  如果是一个集合来求组合的话，就需要startIndex，例如：回溯算法：求组合问题，回溯算法：求组合总和。
  
  如果是多个集合取组合，各个集合之间相互不影响，那么就不用startIndex，例如：回溯算法：电话号码的字母组合
剪枝
去重
- “树枝去重”和“树层去重”。
  
  都知道组合问题可以抽象为树形结构，那么“使用过”在这个树形结构上是有两个维度的，一个维度是同一树枝上“使用过”，一个维度是同一树层上“使用过”。
- 例子：
  - 排序后比较上一个（树层）https://leetcode.com/problems/non-decreasing-subsequences/
  - 用集合去重（树层） https://leetcode.com/problems/non-decreasing-subsequences/
子集问题，收集所有节点的结果（遍历整棵树）
排列问题