一、最长公共子串
1、子串和子序列的区别是什么？最长公共子串问题是什么？
- 子串是连续的子序列
image.png
2、对于上述问题的动态规划三步曲（dp 定义的一切启发）？
- 对于状态定义，如果一维空间就是 dp[i] ，如果是二维空间就是 dp[i][j]，
- 基本套路是让 i 或者 ij 从尾部开始，往前面推衍（比如 i 和 i-1 的关系、如果不选 i 个会怎么样、如果选第 i 个会怎么样）
- 如果是二维的，就让其中一个一维数组从 0 个开始，去遍历另一个一维数组（其实就是两层 for 循环，确定 dp[i][j]）
image.png
3、为什么不定义成 dp[i][j] 是以str1[i]、 str2[j]结尾的最长公共子串呢？
- 因为如果这样定义的话，不容易表示 chars1 取 0 个数据 或者 chars2 取 0 个数据的情况
- 不是一定不行，但是这样就不利于代码的编写
- 所以遇到左开右闭，还是左闭右开；是从 1 到 length +1 ，还是 0 到 length；这些都可以根据题目的具体要求，灵活变动，方便代码的编写和思路梳理
4、最长公共子串的代码实现，单从代码角度，真心是简单的！
image.png
- 时间复杂度 O(n*m)
- 空间复杂度 O(n*m)
5、分析 dp[i][j]的数据存放情况，学会画图也是非常重要的技能，可以帮助分析情况。
image.png
6、通过分析 dp 的分布图，我们发现 dp[i][j] 的计算只依赖于左上角的数值，所以上面空间可以优化成一维数组。
image.png
- 小技巧：并且还发现，可以把 j 倒过来遍历，这样临时变量也省了。
二、01 背包问题
1、什么是 01 背包问题？
image.png
2、状态定义方面的思考
- 处理这种二维的 dp，可以控制其中一维度，让另一维度从 0 开始递增，从而找规律
- 然后观察固定哪一维度，具有 ①最优子结构性 ②无后效性
3、01 背包的动态规划三步曲？
image.png
4、状态定义的思考，是否可以像下面一样，画出 dp[i][j]的状态图？
image.png
5、有没有感觉动态规划就是搞数组？要么搞个 dp[i] 的一维数组，要么搞个 dp[i][j] 的二维数组
- 为什么是搞数组呢？这就是要再次理解下动态规划的概念了
image.png
6、根据动态规划三步曲写出的代码
image.png
7、思考下 01 背包的 i 和 j 可以颠倒顺序吗？
- 不可以，因为动态的是 weights 和 values 才能便于计算
image.png
三、01 背包恰好装满
1、什么是 01 背包恰好装满问题？
image.png
2、观察 dp[i][j]
image.png
3、听说只要改变初始化条件即可
image.png
4、动态规划，只要把现有的题目做好，吃透就行。
- 其他题目也大都类似，再难也不会太难了
