8.动态规划
1. 理论基础¶
动态规划的每一个状态都是由上一个状态推导出来的
动态规划解题五部曲：
- 确定 dp 数组以及下标的含义
- 确定递推公式
- dp数组如何初始化
- 确定遍历顺序
- 举例推导dp数组（打印dp数组）
动态规划 debug：
将 dp 数组打印出来，看看是不是按照自己的思路推导的
自己先思考这三个问题：
- 这道题目我举例推导状态转移公式了么？
- 我打印dp数组的日志了么？
- 打印出来了dp数组和我想的一样么？
2. 斐波那契数列¶
来源：LeetCode 509
动态规划五部曲¶
-
确定 \(dp\) 数组 及其 下标的含义 \(dp[i]\) : 第 \(i\) 个斐波那契数列的数值是 \(dp[i]\)
-
确定递推公式 状态转移方程：\(dp[i] = dp[i-1] + dp[i-2]\)
-
\(dp\) 数组如何初始化 \(dp[0] = 0, dp[1] = 1\)
-
确定遍历顺序 从递归公式 \(dp[i] = dp[i - 1] + dp[i - 2]\) 中可以看出，\(dp[i]\) 是依赖 \(dp[i - 1]\) 和 \(dp[i - 2]\)，因此遍历的顺序一定是从前到后遍历
-
举例推导 \(dp\) 数组 按照递推公式 \(dp[i] = dp[i-1] + dp[i-2]\) ，来推导一下，当 \(N=10\) 的时候，\(dp\) 数组应该是如下的数列： $$ 0 1 1 2 3 5 8 13 21 34 55 $$ 如果代码写出来发现结果不对，就把 \(dp\) 数组打印出来看看和推导的数列是不是一致的。
代码¶
class Solution {
public int fib(int n) {
if (n < 2) return n;
// 确定 dp 数组
int dp[] = new int[n+1];
// 初始化 dp 数组
dp[0] = 0;
dp[1] = 1;
for (int i=2; i<=n; i++){
// 状态转移方程
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}
}
3. 爬楼梯¶
来源：LeetCode 70
思路¶
爬到第一层楼梯有一种方法，爬到二层楼梯有两种方法。
那么第一层楼梯再跨两步就到第三层 ，第二层楼梯再跨一步就到第三层。
所以到第三层楼梯的状态可以由第二层楼梯 和 到第一层楼梯状态推导出来，那么就可以想到动态规划了。
动态规划五部曲¶
-
确定 \(dp\) 数组以及下标的含义 \(dp[i]\) ： 爬到第 \(i\) 层楼梯，有 \(dp[i]\) 种方法
-
确定递推公式 从 \(dp[i]\) 的定义可以看出，\(dp[i]\) 可以有两个方向推出来。
首先是 \(dp[i-1]\) ，上 \(i-1\) 层楼梯，有 \(dp[i-1]\) 种方法，那么再一步跳一个台阶不就是 \(dp[i]\) 了。 其次是 \(dp[i - 2]\) ，上 \(i-2\) 层楼梯，有 \(dp[i - 2]\) 种方法，那么再一步跳两个台阶不就是 \(dp[i]\) 了。
那么 \(dp[i]\) 就是 \(dp[i-1]\) 与 \(dp[i - 2]\) 之和！
所以 \(dp[i] = dp[i - 1] + dp[i - 2]\) 。
-
\(dp\) 数组如何初始化 \(dp[1] = 1\) : 爬到第一层有一种方式 \(dp[2] = 2\) : 爬到第二层有两种方式
-
确定遍历顺序 从递推公式 \(dp[i] = dp[i - 1] + dp[i - 2]\) 中可以看出，遍历顺序一定是从前向后遍历的
-
举例推导 \(dp\) 数组 当 \(n=5\) ，\(dp\) 数组：
代码实现¶
class Solution {
public int climbStairs(int n) {
if (n < 3) return n;
// 定义dp数组
int dp[] = new int[n+1];
// 初始化dp数组
dp[1] = 1;
dp[2] = 2;
// 递推公式
for (int i=3; i<=n; i++){
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}
}
4. 使用最小花费品爬楼梯¶
来源：LeetCode 746
题目重点： “你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯” 也就是相当于 跳到 下标 0 或者 下标 1 是不花费体力的， 从 下标 0 下标1 开始跳就要花费体力了。
动态规划五部曲¶
-
确定 \(dp\) 数组以及下标的含义 使用动态规划，就要有一个数组来记录状态，本题只需要一个一维数组 \(dp[i]\) 就可以了。
\(dp[i]\) 的定义：到达第 \(i\) 台阶所花费的最少体力为 \(dp[i]\)
-
确定递归公式 可以有两个途径得到 \(dp[i]\) ，一个是 \(dp[i-1]\), 一个是 \(dp[i-2]\) (即可以从下标为 \(i-1\) 的台阶爬一个台阶到 第 \(i\) 台阶, 也可以从下标为 \(i-2\) 的台阶跳两个台阶到 第 \(i\) 台阶)：
\(dp[i - 1]\) 跳到 \(dp[i]\) 需要花费 \(dp[i - 1] + cost[i - 1]\)。 \(dp[i - 2]\) 跳到 \(dp[i]\) 需要花费 \(dp[i - 2] + cost[i - 2]\)。
那么究竟是选从 \(dp[i - 1]\) 跳还是从 \(dp[i - 2]\) 跳呢？ 一定是选最小的，所以: $$ dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]) $$ 3. \(dp\) 数组如何初始化 根据递推公式，\(dp[i]\) 由 \(dp[i - 1], dp[i - 2]\) 推出，既然初始化所有的 \(dp[i]\) 是不可能的，那么只初始化 \(dp[0]\) 和 \(dp[1]\) 就够了，其他的最终都是 \(dp[0]\) 和 \(dp[1]\) 推出。
根据 \(dp\) 数组的定义，到达第0台阶所花费的最小体力为 \(dp[0]\)，到达第1台阶所花费的最小体力是 \(dp[1]\) ; 根据题目描述 “你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。” 也就是说到达第 0 个台阶是不花费体力的，但从 第0 个台阶 往上跳的话，需要花费 \(cost[0]\) ；
因此初始化 \(dp[0]=0, dp[1]=0\)
-
确定遍历顺序 因为是模拟台阶，而且 \(dp[i]\) 由 \(dp[i - 1], dp[i - 2]\) 推出，所以是从前到后遍历cost数组就可以了。
-
举例推导 \(dp\) 数组 根据示例2：\(cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]\) 来模拟 \(dp\) 数组的状态变化，如下：
代码实现¶
class Solution {
public int minCostClimbingStairs(int[] cost) {
if (cost.length == 0) return 0;
// 确定dp数组及下标含义
int dp[] = new int[cost.length+1]
// 初始化 dp 数组
dp[0] = 0;
dp[1] = 0;
// 状态转移方程
for (int i=2; i<dp.length; i++){
dp[i] = Math.min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]);
}
return dp[dp.length-1];
}
}
5. 不同路径¶
来源：LeetCode 62
动态规划五部曲¶
-
确定 \(dp\) 数组和下标含义 \(dp[i][j]\) : 二维数组，表示从 \([0, 0]\) 到 \([i, j]\) 的路径数目
-
确定递推公式 因为只能向右或向下走，所以 \([i, j]\) 可以由 \([i-1, j]\) 向右走一步得到, 也可以由 \([i, j-1]\) 向下走一步得到，因此: $$ dp[i][j] = dp[i-1][j] + dp[i][j-1] $$
-
\(dp\) 数组如何初始化 需要初始化最最上层一行和最左边一列: $$ dp[0][j] = 1, dp[i][0] = 1 $$
-
确定遍历顺序 根据递推公式 \(dp[i][j] = dp[i-1][j] + dp[i][j-1]\) , \(dp[i][j]\) 是从上方和左方推导得到的，因此双层遍历，从左到右，从上到下，从而保证在推导 \(dp[i][j]\) 的时候， \(dp[i-1][j]\) 和 \(dp[i][j-1]\) 是有值的
-
举例推导 \(dp\) 数组
代码实现¶
class Solution {
public int uniquePaths(int m, int n) {
// 确定dp数组和下标含义
int dp[][] = new int[m][n];
// 初始化dp数组
// 最上面一层
for (int j=0; j<n; j++) dp[0][j] = 1;
// 最左边一列
for (int i=0; i<m; i++) dp[i][0] = 1;
// 状态转移方程
for (int i=1; i<m; i++){
for (int j=1; j<n; j++){
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
return dp[m-1][n-1];
}
}
6. 不同路径2¶
来源：LeetCode 63
动态规划五部曲¶
-
确定 \(dp\) 数组和下标含义 \(dp[i][j]\) : 二维数组，表示从 \([0, 0]\) 到 \([i, j]\) 的路径数目
-
确定递推公式 因为只能向右或向下走，所以 \([i, j]\) 可以由 \([i-1, j]\) 向右走一步得到, 也可以由 \([i, j-1]\) 向下走一步得到，因此: $$ dp[i][j] = dp[i-1][j] + dp[i][j-1] $$ 但是可能 \([i, j]\) 的位置是障碍物，那么就永远无法从 \([0,0]\) 到 \([i, j]\), 对应的路径数目也就是0，因此此时:
if (obstacleGrid[i][j] == 1) dp[i][j] = 0; -
\(dp\) 数组如何初始化 需要初始化最最上层一行和最左边一列: $$ dp[0][j] = 1, dp[i][0] = 1 $$ 但是如果在最上面一行或者最左边一列中遇到障碍物, 则对于障碍物及其之后的位置都无法到达, 因此路径数目是0，因此初始化代码如下：
for (int j=0; j<n; j++) { if (obstacleGrid[0][j] == 1) { dp[0][j] = 0; break; } else dp[0][j] = 1; } for (int i=0; i<m; i++) { if (obstacleGrid[i][0] == 1) { dp[i][0] = 0; break; } else dp[i][0] = 1; } -
确定遍历顺序 根据递推公式 \(dp[i][j] = dp[i-1][j] + dp[i][j-1]\) , \(dp[i][j]\) 是从上方和左方推导得到的，因此双层遍历，从左到右，从上到下，从而保证在推导 \(dp[i][j]\) 的时候， \(dp[i-1][j]\) 和 \(dp[i][j-1]\) 是有值的
-
举例推导 \(dp\) 数组 对于题目中的示例1，\(dp\) 数组如下：
代码实现¶
class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
// 确定dp数组
int m = obstacleGrid.length;
int n = obstacleGrid[0].length;
int dp[][] = new int[m][n];
// 初始化dp数组
// 如果在最上面一行或者最左边一列中遇到障碍物, 则对于障碍物及其之后的位置都无法到达, 因此路径数目是0
for (int j=0; j<n; j++) {
if (obstacleGrid[0][j] == 1) {
dp[0][j] = 0;
break;
}
else dp[0][j] = 1;
}
for (int i=0; i<m; i++) {
if (obstacleGrid[i][0] == 1) {
dp[i][0] = 0;
break;
}
else dp[i][0] = 1;
}
// 状态转移方程
for (int i=1; i<m; i++){
for (int j=1; j<n; j++){
// 如果是障碍物, 则无法到达该位置, 路径数目是0
if (obstacleGrid[i][j] == 1) dp[i][j] = 0;
else dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
return dp[m-1][n-1];
}
}
7. 整数拆分¶
来源：LeetCode 343
动态规划五部曲¶
1. 确定 \(dp\) 数据以及下标的含义
\(dp[i]\) : 分拆数字 \(i\) , 可以得到的最大乘积为 \(dp[i]\)
这个定义非常重要，说明至少会将 \(i\) 拆成两个整数
2. 确定递推公式
如何得到 \(dp[i]\) ?
首先可以将 \(i\) 拆成两部分，一部分是 \(j\), 另一部分就是 \(i - j\) , 然后从 \(1\) 开始遍历，即使得 \(1<=j<i\) （这个时候是将 \(i\) 拆分成了两个整数）, 此时：\(dp[i] = j * (i-j)\) .
其次可以将 \(i\) 拆分成 3个甚至更多的整数，这个时候 \(j\) 不变，仍然是从 \(1\) 开始遍历（\(1<=j<i\)）, 将 \(i-j\) 进行进一步拆分，那么对 \(i-j\) 拆分得到的最大乘积为 \(dp[i-j]\) , 因此此时： \(dp[i] = j * dp[i-j]\)
补充：什为么不对 \(j\) 进行进一步拆分？ （1）\(j\) 是从 1 开始遍历，拆分 \(j\) 的情况，在遍历j的过程中其实都计算过了 （2） \(j * (i - j)\) 是单纯的把整数拆分为两个数相乘，而 \(j * dp[i - j]\)是拆分成两个以及两个以上的个数相乘，如果定义\(dp[i - j] * dp[j]\) 默认将一个数强制拆成4份以及4份以上了
综上，递推公式为： $$ dp[i]= max(j * (i-j), j * dp[i-j], dp[i]) $$
3. 如何对 \(dp\) 数组进行初始化？
\(dp[0],\ dp[1]\) 应该初始化多少呢？
严格从 \(dp[i]\) 的定义来说，\(dp[0],\ dp[1]\) 就不应该初始化，也就是没有意义的数值。 拆分0和拆分1的最大乘积是多少？这是无解的。
因此从 \(dp[2]\) 开始初始化： $$ dp[2] = 1 $$
4. 确定遍历顺序
根据递归公式：\(dp[i]= max(j * (i-j), j * dp[i-j], dp[i])\) ,
\(dp[i]\) 是依靠 \(dp[i - j]\) 的状态，所以遍历一定是从前向后遍历，先有 \(dp[i - j]\) 再有 \(dp[i]\) 。
5. 举例推导dp数组
当 \(n=10\), \(dp\) 数组如下：
代码实现¶
class Solution {
public int integerBreak(int n) {
// 确定dp数组
int dp[] = new int[n+1];
// 初始化dp数组
dp[2] = 1;
// 状态转移方程
for (int i=3; i<=n; i++)
for (int j=1; j<i; j++){
// j从1开始, 从0开始的话，那么拆分一个数拆出个0，求最大乘积就没有意义了
dp[i] = Math.max(dp[i], Math.max(j * (i-j), j * dp[i-j]));
}
return dp[n];
}
}
8. 不同的二叉搜索树¶
思路¶
先尝试画图寻找规律
\(n\) 为 \(1\) 的时候有一棵树，\(n\) 为 \(2\) 有两棵树，这个是很直观的。
\(n\) 为 \(0\) 的时候是空二叉树，也可以算是一棵二叉搜索树
当 \(1\) 为头结点的时候，其右子树有两个节点，这两个节点的布局 和 \(n\) 为 \(2\) 的时候两棵树的布局是一样的！
虽然节点数值不一样，但是我们是求不同树的数量，并不用把搜索树都列出来，所以不用关心其具体数值的差异
当 \(3\) 为头结点的时候，其左子树有两个节点，这两个节点的布局 和 \(n\) 为 \(2\) 的时候两棵树的布局也是一样的！
当2为头结点的时候，其左右子树都只有一个节点，布局 和 \(n\) 为 \(1\) 的时候只有一棵树的布局也是一样的！
发现到这里，就找到了重叠子问题了，其实也就是发现 可以通过 \(dp[1]\) 和 \(dp[2]\) 来推导出来 \(dp[3]\) 的某种方式。
思考到这里，这道题目就有眉目了！！！
\(dp[3]\) 即是 元素1为头结点搜索树的数量 + 元素2为头结点搜索树的数量 + 元素3为头结点搜索树的数量
元素1为头结点搜索树的数量 = 右子树有2个元素的搜索树数量 * 左子树有0个元素的搜索树数量 元素2为头结点搜索树的数量 = 右子树有1个元素的搜索树数量 * 左子树有1个元素的搜索树数量 元素3为头结点搜索树的数量 = 右子树有0个元素的搜索树数量 * 左子树有2个元素的搜索树数量
有2个元素的搜索树数量就是 \(dp[2]\) 有1个元素的搜索树数量就是 \(dp[1]\) 有0个元素的搜索树数量就是 \(dp[0]\) 所以: \(dp[3] = dp[2] * dp[0] + dp[1] * dp[1] + dp[0] * dp[2]\)
动态规划五部曲¶
1. \(dp\) 数组以及下标的含义
\(dp[i]\) : 以数值 1 到 \(i\) 为节点组成的二叉搜索树的个数为 \(dp[i]\), 也可以理解成 \(i\) 个不同元素组成的二叉搜索树的二叔
2. 确定 递归公式
\(dp[i]\) : 元素 \(1\) 为头节点的二叉搜索树的数量 + 元素 \(2\) 为头节点的二叉搜索树的数量 + ...... + 元素 \(i\) 为头节点的二叉搜索树的数量
其中如果元素 \(j\) 为头节点, 根据二叉搜索树的定义，则左子树有 \(j-1\) 个节点，右子树有 \(i-j\) 个节点，那么元素 \(j\) 为头节点的二叉搜索树的数量 \(dp[j] = dp[j-1] ** dp[i-j]\)
\(dp[i]\) 一开始为 0， 从 1 到 \(i\) 对 \(j\) 进行遍历，那么递推公式为： $$ dp[i] = dp[0]dp[i-1] + dp[1]dp[i-2] + ... + dp[i-1]*dp[0] $$ 进行简化：
for (int j=1; j<=i; j++){
dp[i] = dp[i] + dp[j-1] * dp[i-j]
}
3. 初始化 \(dp\) 数组
只需要初始化 \(dp[0]\), \(0\) 个节点的二叉搜索树数量，空节点也是二叉搜索树，因此： $$ dp[0] = 1 $$
4. 确定遍历顺序
首先一定是遍历节点数，从递归公式：\(dp[i] = dp[i] + dp[j - 1] * dp[i - j]\) 可以看出，节点数为 \(i\) 的状态是依靠 \(i\) 之前节点数的状态，因此从后向前进行遍历。
for (int i=1; i<=n; i++){
// 以 1到i分别为头节点
for (int j=1; j<=i; j++){
dp[i] += dp[j-1] * dp[i-j];
}
}
5. 举例推导 \(dp\) 数组
\(n=5\), \(dp\) 数组如下：
代码实现¶
class Solution {
public int numTrees(int n) {
// 确定dp数组
int dp[] = new int[n+1];
// 初始化dp数组
dp[0]=1;
// 状态转移方程
// 从前向后进行遍历
for (int i=1; i<=n; i++)
// 以 1到i分别为头节点
for (int j=1; j<=i; j++){
dp[i] += dp[j-1] * dp[i-j];
}
return dp[n];
}
}