动态规划

约 4209 字大约 14 分钟

2025-02-27

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])
$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. 不同的二叉搜索树

LeetCode 96

思路

先尝试画图寻找规律

$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];

    }

}

9. 背包理论基础1

版权所有

版权归属：cloudinwind

本文链接：/review/2ha5v0zt/

许可证：署名-非商业性-相同方式共享 4.0 国际 (CC-BY-NC-SA-4.0)