动态规划

Ruochen Chen2025年5月12日大约 14 分钟

动态规划

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

确定递推公式

dp数组如何初始化

确定遍历顺序

举例推导dp数组

返回结果是看遍历顺序如何推倒的

背包问题

背包类型	问题类型	推荐数组类型	遍历顺序	是否倒序容量	状态转移方程
01背包	价值最大	一维 / 二维	先物品，再容量	✅（一维需要）❌（二维不需要）	`dp[j] = max(dp[j], dp[j-w] + v)`
完全背包	价值最大	一维 / 二维	先物品，再容量（正序）	❌	`dp[j] = max(dp[j], dp[j-w] + v)`
完全背包	组合数	一维 / 二维	先物品，再容量（正序）	❌	`dp[j] += dp[j-w]`
完全背包	排列数	一维	先容量，再物品（正序）	❌	`dp[j] += dp[j-w]`

✅ 01背包一维数组要倒序，防止同一轮多次选同一个物品。
❌ 二维数组不需要倒序，因为每层是独立的，不会重复使用。
✅ 完全背包组合数是“先物品再容量”，保证每种组合只计算一次。
✅ 完全背包排列数是“先容量再物品”，考虑顺序不同的情况。

股票交易

题号	限制条件	状态定义 `dp[i][k][h]`	状态转移方程	初始状态
121 买卖一次	最多 1 次交易	`dp[i][0]`：不持股 `dp[i][1]`：持股	`dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])` `dp[i][1] = max(dp[i-1][1], -prices[i])`	`dp[0][0] = 0` `dp[0][1] = -prices[0]`
122 无限次交易	不限制交易次数	同上	`dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])` `dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])`	同上
123 最多 2 次	`k=0/1/2`, 三维（也可以枚举所有的dp数组）	`dp[i][k][h]`	`dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])` `dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])`	初始化 `dp[0][k][1] = -prices[0]`，`dp[0][k][0] = 0`
188 最多 k 次交易	任意 k 值	同上, 必须三维因为无法枚举	同 123	同 123
309 含冷冻期	卖出后 1 天不能买入	`dp[i][0]`：不持股 `dp[i][1]`：持股 `dp[i][2]`：冷冻期	`dp[i][0] = max(dp[i-1][0], dp[i-1][2])` `dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])` `dp[i][2] = dp[i-1][1] + prices[i]`	`dp[0][0] = 0`, `dp[0][1] = -prices[0]`, `dp[0][2] = 0`
714 含手续费	每次交易扣 fee	`dp[i][0]`：不持股 `dp[i][1]`：持股	`dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i] - fee)` `dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])`	同 121

子序列问题

最长递增子序列

定义dp数组：dp[i]是以nums[i]为结尾的最长递增子序列的长度
递推公式（状态转移方程）：如果nums[i]>nums[j]，dp[i]=max(dp[j]+1,dp[i])，要想到dp[i]由哪些状态可以推出来，并取最大值
初始化：dp[i]=1，至少长度都包含nums[i]，一个元素结尾长度就是1
遍历顺序：从小到大遍历，因为推出后面的元素需要依赖前面的元素结果

for (int i = 1; i < dp.length; i++) { // i从1开始 因为dp[0]肯定是1
        for (int j = 0; j < i; j++) { // j其实就是遍历0到i-1 比较i前的所有元素（用j遍历的）
            // 递推公式
        }
    res = Math.max(res, dp[i]); // 存入结果，注意结果不是dp[nums.size-1]
}

打印dp检查

最长连续递增子序列

定义dp数组：dp[i]是以nums[i]为结尾的最长连续递增子序列的长度
递推公式（状态转移方程）：只比较i和i-1的位置，不需要向上一题比较i前的所有元素（用j遍历的）。如果nums[i]>nums[i-1]，dp[i]=dp[i-1]+1
初始化：dp[i]=1，至少长度都包含nums[i]，一个元素结尾长度就是1
遍历顺序：从小到大遍历，因为推出后面的元素需要依赖前面的元素结果

for (int i = 1; i < dp.length; i++) { // i从1开始 因为dp[0]肯定是1
    // 递推公式
    res = Math.max(res, dp[i]); // 存入结果，注意结果不是dp[nums.size-1]
}

打印dp检查

最长重复子数组（元素要求连续）

定义dp数组：以下标i - 1为结尾的nums1，和以下标j - 1为结尾的nums2，最长重复子数组长度为dp[i][j]。这样做简便初始化，不然如果以i和j结尾，又要循环遍历看有没有相等的第一个元素，要对第一行和第一列进行初始化，如果有还得初始化为1。但是现在就可以直接初始化为0
递推公式（状态转移方程）：根据dp[i][j]的定义，dp[i][j]的状态只能由dp[i - 1][j - 1](也就是左上角)推导出来。即当nums1[i - 1] 和nums2[j - 1]相等的时候，dp[i][j] = dp[i - 1][j - 1] + 1
初始化：dp[i][0] 和dp[0][j]初始化为0，因为求最长是从0开始加。其他地方初始化多少无所谓会被覆盖
遍历顺序：外层for循环遍历nums1，内层for循环遍历nums2，反过来也可以没区别

for (int i = 1; i <= nums1.size(); i++) { //从1开始因为`dp[i][0]` 和`dp[0][j]`初始化为0，而且实际上根据dp定义这俩没有意义
    for (int j = 1; j <= nums2.size(); j++) { // <=nums.size是因为dp数组的定义
        // 递推公式
        if (dp[i][j] > result) result = dp[i][j]; //遍历二维数组，找出最长重复子数组，结果并不是dp[nums1.size][nums2.size]
    }
}

打印dp检查

最长公共子序列（元素可以不连续，顺序保证即可）

定义dp数组：长度为[0, i - 1]的字符串nums1与长度为[0, j - 1]的字符串nums2的最长公共子序列为dp[i][j]，这样做简便初始化，不然如果以i和j结尾，又要循环遍历看有没有相等的第一个元素，要对第一行和第一列进行初始化
递推公式（状态转移方程）：如果nums1[i - 1] 与 nums2[j - 1]相同，那么找到了一个公共元素，所以dp[i][j] = dp[i - 1][j - 1] + 1; 如果nums1[i - 1] 与 nums2[j - 1]不相同，那就看看nums1[0, i - 2]与nums2[0, j - 1]的最长公共子序列和 nums1[0, i - 1]与nums2[0, j - 2]的最长公共子序列，取最大的。

if (nums1[i - 1] == nums2[j - 1]) {
    dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}

初始化：第一行和第一列，nums1[0, i-1]和空串的最长公共子序列自然是0，所以dp[i][0] = 0; 同理dp[0][j]也是0。所以第一行第一列都是0。其他地方初始化多少无所谓会被覆盖
遍历顺序：从坐向右，从上到下

for (int i = 1; i <= nums1.size(); i++) {
            for (int j = 1; j <= nums2.size(); j++) {
                // 递推公式
            }
}
return dp[text1.size()][text2.size()] // 结果

打印dp检查

不相交的线

其实就是找两个数组的最长公共子序列
公共子序列他们的线不会相交

最大子序和（连续的和）

定义dp数组：包括下标i（以nums[i]为结尾）的最大连续子序列和为dp[i]
递推公式（状态转移方程）：dp[i]只有两个方向可以推出来：dp[i - 1] + nums[i]，即：nums[i]加入当前连续子序列和，或者nums[i]，即：从头开始计算当前连续子序列和。dp[i] = max(dp[i - 1] + nums[i], nums[i])
初始化：从递推公式可以看出来dp[i]是依赖于dp[i - 1]的状态，dp[0]就是递推公式的基础。dp[0] = nums[0]
遍历顺序：递推公式中dp[i]依赖于dp[i - 1]的状态，需要从前向后遍历。

int result = dp[0];
for (int i = 1; i < nums.size(); i++) {
    // 递推公式
    if (dp[i] > result) result = dp[i]; // result 保存dp[i]的最大值
}

打印dp检查

编辑距离问题

s删除元素让s变成t t是子数组

判断子序列

定义dp数组：dp[i][j] 表示以下标i-1为结尾的字符串s，和以下标j-1为结尾的字符串t，相同子序列的长度为dp[i][j]。方便第一行第一列初始化
递推公式（状态转移方程）：if (s[i - 1] == t[j - 1])，那么dp[i][j] = dp[i - 1][j - 1] + 1，if (s[i - 1] != t[j - 1])，此时相当于t要删除元素，t如果把当前元素t[j - 1]删除，那么dp[i][j] 的数值就是看s[i - 1]与 t[j - 2]的比较结果了，即：dp[i][j] = dp[i][j - 1]
初始化：从递推公式可以看出dp[i][j]都是依赖于dp[i - 1][j - 1] 和 dp[i][j - 1]，所以dp[0][0]和dp[i][0]是一定要初始化的。
遍历顺序：根据递推公式推倒方向得出

for(int i = 1; i <= length1; i++){
    for(int j = 1; j <= length2; j++){
        // 递推公式
    }
}
if(dp[length1][length2] == length1){
    return true;
}else{
    return false;
}

打印dp检查

不同的子序列（s有多少删除元素的方式能变成t？）

定义dp数组：以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]
递推公式（状态转移方程）：当s[i - 1] 与 t[j - 1]相等时，dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]; 当s[i - 1] 与 t[j - 1]不相等时，dp[i][j]只有一部分组成，不用s[i - 1]来匹配（就是模拟在s中删除这个元素），即：dp[i - 1][j]。所以dp[i][j] = dp[i - 1][j]
初始化：
- dp[i][0]一定都是1，因为也就是把以i-1为结尾的s，删除所有元素，出现空字符串的个数就是1。
- dp[0][j]一定都是0，s如论如何也变成不了t。
- dp[0][0]应该是1，空字符串s，可以删除0个元素，变成空字符串t。
遍历顺序：

for (int i = 1; i <= s.size(); i++) {
    for (int j = 1; j <= t.size(); j++) {
        // 递推公式
    }
}
return dp[s.size()][t.size()];

打印dp检查

两个字符串的删除操作（可以用删，问最少操作次数）

定义dp数组：dp[i][j]：以i-1为结尾的字符串word1，和以j-1位结尾的字符串word2，想要达到相等，所需要删除元素的最少次数。
递推公式（状态转移方程）：
- 当word1[i - 1] 与 word2[j - 1]相同的时候，dp[i][j] = dp[i - 1][j - 1]; 因为不需要操作，可以从上一个位置推出当前结果
- 当word1[i - 1] 与 word2[j - 1]不相同的时候，有三种情况：取最小值因为求的是最小操作次数
  - 情况一：删word1[i - 1]，最少操作次数为dp[i - 1][j] + 1
  - 情况二：删word2[j - 1]，最少操作次数为dp[i][j - 1] + 1
  - 情况三：同时删word1[i - 1]和word2[j - 1]，操作的最少次数为dp[i - 1][j - 1] + 2
初始化：dp[i][0]：word2为空字符串，以i-1为结尾的字符串word1要删除多少个元素，才能和word2相同呢，很明显dp[i][0] = i。dp[0][j]的话同理
遍历顺序：

for (int i = 1; i <= word1.size(); i++) {
            for (int j = 1; j <= word2.size(); j++) {
                // 递推公式
            }
}
return dp[word1.size()][word2.size()];

打印dp检查

编辑距离（可以用增删改，问最少操作次数）

定义dp数组：以下标i-1为结尾的字符串word1，和以下标j-1为结尾的字符串word2，最近编辑距离为dp[i][j]
递推公式（状态转移方程）：
- 当word1[i - 1] 与 word2[j - 1]相同的时候，dp[i][j] = dp[i - 1][j - 1];
- 当word1[i - 1] 与 word2[j - 1]不相同的时候，有三种情况：取最小
  - 操作一：word1删除一个元素，那么就是以下标i - 2为结尾的word1 与 j-1为结尾的word2的最近编辑距离再加上一个操作。即 dp[i][j] = dp[i - 1][j] + 1;
  - 操作二：word2删除一个元素，那么就是以下标i - 1为结尾的word1 与 j-2为结尾的word2的最近编辑距离再加上一个操作。即 dp[i][j] = dp[i][j - 1] + 1;
    - word2添加一个元素，相当于word1删除一个元素
  - 一次替换的操作，就可以让 word1[i - 1] 和 word2[j - 1] 相同。所以 dp[i][j] = dp[i - 1][j - 1] + 1;
初始化：dp[i][0]：word2为空字符串，以i-1为结尾的字符串word1要删除多少个元素，才能和word2相同呢，很明显dp[i][0] = i。dp[0][j]的话同理
遍历顺序：

for (int i = 1; i <= word1.size(); i++) {
            for (int j = 1; j <= word2.size(); j++) {
                // 递推公式
            }
}
return dp[word1.size()][word2.size()];

打印dp检查

回文子串（要连续）

定义dp数组：区间范围[i,j] （注意是左闭右闭，包含）的子串是否是回文子串，如果是dp[i][j]为true，否则为false。
递推公式（状态转移方程）：
- s[i]与s[j]不相等，dp[i][j]一定是false
- 相等三种情况定义一个result然后++
  - 情况一：下标i 与 j相同，同一个字符例如a，当然是回文子串
  - 情况二：下标i 与 j相差为1，例如aa，也是回文子串
  - 情况三：下标：i 与 j相差大于1的时候，例如cabac，此时s[i]与s[j]已经相同了，我们看i到j区间是不是回文子串就看aba是不是回文就可以了，那么aba的区间就是 i+1 与 j-1区间，这个区间是不是回文就看dp[i + 1][j - 1]是否为true。
初始化：dp[i][j]初始化为false
遍历顺序：要从下到上，从左到右遍历，这样保证dp[i + 1][j - 1]都是经过计算的

for (int i = s.size() - 1; i >= 0; i--) {  // 注意遍历顺序
    for (int j = i; j < s.size(); j++) {
        // 递推公式
    }
}

打印dp检查

最长回文子序列（可以不连续）

定义dp数组：字符串s在[i, j]范围内最长的回文子序列的长度为dp[i][j]。
递推公式（状态转移方程）：
- 如果s[i]与s[j]相同，那么dp[i][j] = dp[i + 1][j - 1] + 2;
- 如果s[i]与s[j]不相同，说明s[i]和s[j]的同时加入并不能增加[i,j]区间回文子序列的长度，那么分别加入s[i]、s[j]看看哪一个可以组成最长的回文子序列，即：dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
初始化：当i与j相同，那么dp[i][j]一定是等于1的，即：一个字符的回文子序列长度就是1。dp[i][i] = 1
遍历顺序：dp[i][j] 依赖于 dp[i + 1][j - 1] ，dp[i + 1][j] 和 dp[i][j - 1]。从下到上遍历，这样才能保证下一行的数据是经过计算的。

for (int i = s.size() - 1; i >= 0; i--) {
    for (int j = i + 1; j < s.size(); j++) { //j=i已经初始化
        // 递推公式
    }
}
return dp[0][s.size() - 1]; //最终答案在右上角

打印dp检查

马跳棋的跳法数量

定义dp数组：dp[x][y][step] 表示从(0,0)到(x,y)用step步的方法数
递推公式：
- 马可以跳到8个方向
- 如果马跳到(x,y)，那么(x,y)可以跳到8个方向
- 所以dp[x][y][step] = dp[x-1][y-2][step-1] + dp[x-1][y+2][step-1] + dp[x+1][y-2][step-1] + dp[x+1][y+2][step-1] + dp[x-2][y-1][step-1] + dp[x-2][y+1][step-1] + dp[x+2][y-1][step-1] + dp[x+2][y+1][step-1]
初始化：dp[0][0][0] = 1
遍历顺序：从(0,0)开始遍历

// 马的8个可能移动方向
int[] dx = {-2, -1, 1, 2, 2, 1, -1, -2};
int[] dy = {-1, -2, -2, -1, 1, 2, 2, 1};

// 动态规划填表
for (int step = 1; step <= k; step++) {
    for (int x = 0; x < 10; x++) {
        for (int y = 0; y < 10; y++) {
            // 尝试从8个方向跳到当前位置(x, y)
            for (int i = 0; i < 8; i++) {
                int prevX = x - dx[i];
                int prevY = y - dy[i];
                
                // 检查前一个位置是否在棋盘范围内
                if (prevX >= 0 && prevX < 10 && prevY >= 0 && prevY < 10) {
                    dp[x][y][step] += dp[prevX][prevY][step - 1]; // 把所有上一步（step-1）可以跳到 (x, y) 的位置 (prevX, prevY) 的跳法数，累加到当前位置的跳法数上。
                }
            }
        }
    }
}