动态规划

2026-04-24 2026-04-24

动态规划

1 解题步骤

Dynamic Programming 动态规划

真正理解 DP 应该注意一下几点：

DP 数组中每一个值，或者索引的意义
递推公式
DP 数组的如何初始化
遍历顺序
打印 DP 数组（主要用于分析错误）

1.1 什么时候用

判断所有可能的状态中（图）是不是有环，有环一定不是 DP
数据量极大的情况下不太能用 DP

DP 的核心是，递推关系要固定不变，能找到让关系保持不变的 dp 数组定义，这点也是最难的

2 背包问题

2.1 零一背包（二维数组）

给定 n 件物品，每件物品有价值 value[i] 和重量 weight[i] 在容量为 W 的背包中选择若干件物品，使得总价值最大，每件物品最多选一次。

先用没有空间简化的方式进行分析（二维 dp）

数组的定义：[0, i] 个物品，任选放入容量为 j 背包中的最大价值为 dp[i][j]
递推公式：

不放物品 i 则和 i - 1 一致
如果放入 dp[i - 1][j - weight[i]] + value[i]，也就是不放入之前的最大价值（注意要改重量）+ 放入后的最大价值
取上述两种情况的最大值，就是递推公式
记得需要检查 j - weight[i]] + value[i]是否成立，也就是当前容量是否能够放入这个物品

初始化需要先分析递推公式需要的前置条件

需要的是 [i - 1][j] 或者 [i - 1][j - n] 的数据，因此初始化横纵坐标即可
其他位置初始化，实际上这个值和后面的求值没有关系，初始化为任何值都可以
其实初始化还可以横纵坐标都用 0 作为边界条件，不过代码随想录里并没有这么做

遍历顺序，根据递推公式前置条件可以得到，实际上二维 dp 是没有顺序要求的，正序倒序以及背包物品顺序都可以颠倒

// 假设：dp 的维度是 dp[N][C+1]，并且已初始化为 0
// dp[i][j]：用前 i 个物品（下标 0..i），在容量 j 下的最大价值

for (int j = 0; j <= C; j++) {
    if (j >= w[0]) dp[0][j] = v[0];
    // else dp[0][j] = 0;  // 已初始化可省略
}

for (int i = 1; i < N; i++) {
    for (int j = 0; j <= C; j++) {
        dp[i][j] = dp[i-1][j];  // 不选第 i 个，先继承
        if (j >= w[i]) {
            dp[i][j] = max(dp[i][j], dp[i-1][j - w[i]] + v[i]);  // 选第 i 个
        }
    }
}

2.2 零一背包（滚动数组）

可以发现一个问题，就是 dp[i] 一直使用的是 dp[i - 1] 相关的数据进行计算的

但是要注意遍历的顺序，检查递推公式：dp[i - 1][j - weight[i]] + value[i] 和 dp[i - 1][j] 其中之一，可以发现j 依赖于上一轮次的 j 或者 j - weight[i]，这两个都是小于等于 j 的，因此 dp[j] 的遍历要用到上一轮的更小值，应该是从大到小遍历才可以！

数组定义：在第 i 次循环中dp[j] 容量为 j 的背包的最大价值
递推公式：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]) （注意其实 i 这个索引还是存在的，只是把 p 数组压缩一个维度）
初始化：dp[0]肯定是 0，其他数值初始化为可能的数值中的最小值（为了防止覆盖其他值），看题目，一般也是 0
遍历顺序：先遍历物品数量，再遍历背包容量，第二层循环需要倒序（因为不可以对依赖项进行覆写）

代码部分可以参考本文中 分割等和子集 题目

// w 和 v 下标从 0 开始
for (int i = 0; i < N; i++) {
    for (int j = C; j >= w[i]; j--) {
        dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
    }
}

2.3 完全背包

每一个物品可以使用无数次的背包

对于二维的情况下，直接改成就是完全背包，表示允许重复选取某一个数

dp[i][j] = max(
    dp[i-1][j],                 // 不选第 i 个物品
    dp[i][j - w[i]] + v[i]      // 选第 i 个物品（可重复）
)

把内层 for 循环改成正序遍历就可以让物品使用无限次

for (int i = 0; i < N; ++i) {
    for (int j = w[i]; j <= C; ++j) {
        dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
    }
}

这里要明确清楚为什么，因为在正序遍历的时候 dp[j - w[i]] + v[i]这个数值中的 dp[j - w[i]] 是在本轮（外层 i 循环）之前遍历的，有可能是已经添加过物品 i 的一个状态。这时候的递推是基于本轮的状态实现的，可以在此基础上再添加一个物品 i，因此就构成了每个物品可以无限取用的情况，也就是完全背包

另外要注意一点：纯完全背包的遍历顺序（物品和背包）是可以颠倒的！

原因就是一个：递推公式中可以由前面的数值推出当前的数值，我的建议是如果理解的话还是需要手动模拟一下横纵的顺序，就可以发现颠倒顺序后仍然可以用前面的状态推出当前的状态

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

2.4 完全背包的排列组合

但是如果涉及到了排列组合问题，就会导致遍历顺序需要注意

假设我们的物品重量为 w[] = [1, 2, 3];，对于取物品恰好满足和为 target 的题目，递推公式为dp[j] += dp[j - w[i]];

这个递推公式是通用的，关键在于 dp[j - w[i]]代表的数值是什么

对于 先遍历物品后遍历背包的场景（01 背包通用方式）：

在 1 物品选择依次放满所有的背包
在 12 物品中选择依次放满，这个情况下只会有先 1 后 2的放入情况

意思是放入 2 以后，必定只会放入 >= 2 的物品，不会再回去放入 1，这种情况是组合

对于 先遍历背包后遍历物品的场景：

我认为这个有点抽象，所以这里用了手写的方式来解释

这里 dp 数组中是一个个确认过去的，内层循环中会反复对同一个 dp[j] 进行状态的累加，因此参考下图可以发现重叠的问题

就是因为取物品的顺序不是固定的，i 的循环表示最后补上这个物品（没有圈的数值），但这就会导致每个物品都有可能为那个“补充值”，但是补充值本身会在 0 + j的情况下被计算一次：

举例来说：3 = 1 + 2，这里的 2 当做“补充值”，表示在所有和为 1 的情况上末尾补充一个 2 可以达成和为 3，但是当我们求补充值为 1 的时候，计算所有和为 2 的情况个数的时候，会和补充值为 2 的情况重复

3 股票问题

股票问题的关键仍然在于 dp 数组的定义

定义 dp[i][0] 和 dp[i][1] 分别表示股票的持有和未持有，而不是统计买入与卖出，这是唯一的关键

4 子序列问题

如果是连续子序列问题，可以查看 KMP 算法

如果是两个字符串相关的比较，将连个字符串构成一个二维的数组可罗列所有的状态

一般来说永远推荐把 dp[j]定义为 nums[j - 1]为结尾的 xxx 状态，这样可以省去一个初始化特判的过程

之后的 for 循环只需要从 1 遍历到 nums.size() + 1即可

4.1 LCS 最长子序列

最长子序列问题：考虑删除这唯一一个操作

删除表示不在某一个字符串中考虑这个字符，也就是在对应的 dp 数组中向上回退一个数字

不同的题目需要注意删除这个操作对 dp 数组内容的影响

4.2 编辑距离

编辑距离就是删除操作会导致一个操作数 + 1

编辑距离的另一个主要特点就是：操作是相互的，也就是删除 a 的一个元素，等价于给 b 增加一个元素

另外，如果替换一个字符，等于消耗一个操作，将两个字符变成相等

因此总结来看，终究还是删除和相等两种操作，关键在于需要学会定义 dp 数组为 nums[i - 1] 对应的 xxx

4.3 回文串

回文串的特点是他的状态转移不是取决于某一个值的加入，而是第一个值和最后一个值的加入

意思是状态转移时设定 dp[i][j] 代表 [i, j) 的字符串是不是回文串的时候，其依赖的状态是 dp[i + 1][j - 1]

5 经典题目

之前从来没有接触过动态规划，所以可能选择的题目相对多一些

5.1 爬楼梯

LeetCode 70

统计爬楼梯次数，例如第 3 层只能由第 2 层或者第 1 层爬上来，这就构成了递推关系

dp 数组：索引代表第几个台阶，数值代表需要的步数
递推公式：上两个台阶的次数求和
数组初始化：dp[1] = 1, dp[2] = 2
遍历顺序：顺序

如果使用循环变量的方式，实际使用方法是和斐波那契的反过来的（因为初始值不同了所有有影响）

其实 dp 的题目也不一定要优化，那样初始化逻辑会更加清晰明了

class Solution {
public:
    int climbStairs(int n) {
        // 同样使用两个内存就可以了
        vector<int> dp(2, 0);
        dp[0] = 1;
        dp[1] = 2;

        int ret = 0;
        if (n < 3) return n;
        for (int i = 2; i < n; i++) {
            // 注意这里的滚动
            ret = dp[0] + dp[1];
            dp[0] = dp[1];
            dp[1] = ret;
        }
        return ret;
    }
};

5.2 不同的二叉搜索树

LeetCode 96

可能从这里开始递归关系相对开始复杂了

遍历所有数值作为根节点，然后左右子树的 dp 数量相乘

这里似乎能够看出来，dp 的本质是用过去的状态推导现在的状态（有点像递归经典汉诺塔？）

class Solution {
public:
    int numTrees(int n) {
        vector<int> dp(n + 1 , 0);
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i < n + 1; i++) {
            for (int j = 1; j <= i; j++) {
                // 左右子树分别数量相乘
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }
        return dp[n];
    }
};

5.3 分割等和子集

LeetCode 416

这是一个 01 背包问题，将数值同时视作价值和重量，在理解这个的问题上花了很多时间，实际上是在给定的上限中尽可能的取到最靠近上限的指标，只不过上限和指标都是同一个数值组成的

如果把容量和价值都设置为数值，那么就指的是在给定的上限下，取到最靠近上限的一个值

dp 数组的含义是背包容量为 j 能够装下物品的最大价值，

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        // 01 背包，容量和价值相等，滚动数组方式
        int sum = 0;
        for (int& a : nums) sum += a;
        if (sum % 2) return false;
        // 容量下标直接代表容量，所以要 + 1
        int items = nums.size();
        int volume = sum / 2;
        vector<int> dp(volume + 1, 0);

        // 初始化应该全部是0，已经完成了
        for (int i = 0; i < items; i++) {
            for (int j = volume; j>= nums[i]; j--) {
                // 这里要保证当前物品放得进去，并把判断放进循环
                    dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]); // 这里第二个 num[i] 是价值
            }
        }
        return dp[volume] == volume;
    }
};

5.4 目标和

LeetCode 494

本题的关键点在于，所有的正数之和应该等于 (sum + target) / 2，随后转化为 01 背包问题

指定 dp 数组的含义是 dp[i][j] 代表选取前 i 个物品构成和为 j 的可能性计数

可以得到递推公式 dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]]，分别表示是否加入当前数组

随后就可以简化为一维数组

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum = 0;
        for (int &a : nums) sum += a;
        // 如果 target 绝对值大于 sum，肯定无解
        if (abs(target) > sum) return 0;
        if ((sum + target) % 2 != 0) return 0;
        int pos = (sum + target) / 2;  // 所有被赋予正号的数之和

        vector<int> dp(pos + 1, 0);
        dp[0] = 1; // 装满容量为 0 的背包有 1 种方法：什么都不选

        for (int i = 0; i < (int)nums.size(); i++) {
            for (int j = pos; j >= nums[i]; j--) {
                // 当前位置 j 的方案数 += 选择当前物品后的方案数
                dp[j] += dp[j - nums[i]];
            }
        }
        return dp[pos];
    }
};

5.5 完全平方数

LeetCode 279

注意递推关系， + 1 并取最最小值

class Solution {
public:
    int numSquares(int n) {
        // 完全背包，最小值
        int max = sqrt(n) + 1;
        vector<int> dp(n + 1, INT_MAX);
        dp[0] = 0;
        for (int i = 1; i <= max; i++) {
            int sq = i * i;
            for (int j = sq; j <= n; j++) {
                    dp[j] = min(dp[j], dp[j - sq] + 1); // 不要忘了这里 + 1
            }
        }
        return dp[n];
    }
};

5.6 单词拆分

本质还是把每一个小词当作一个物品，背包容量是整个字符串

这里可以记忆一下 string 的库函数比较

s.compare(pos, len, target) 表示从字符串 s 的位置 pos 开始，取长度 len 的字串进行比较 target

注意这个返回值是 int 不是 bool ，在两者相等的时候返回 0

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        int n = s.size();
        vector<bool> dp(n + 1, false);
        dp[0] = true;

        for (int j = 1; j <= n; j++) {
            for (const auto& w : wordDict) {
                int len = w.size();
                if (j >= len && dp[j - len]) {
                    // s 的子串 [j-len, j) 是否等于 w
                    if (s.compare(j - len, len, w) == 0) {
                        dp[j] = true;
                        break;
                    }
                }
            }
        }
        return dp[n];
    }
};

5.7 打家劫舍 III

LeetCode 337

树形 dp 的基础题目，之前一直使用的是在一维数组中进行 dp 的规划，现在是树形中的

通过递归可以实现每个层单独一个 dp 数组，但是因为递归会自动保留参数，所以每层中间信息是共享的

dp[0] 是不偷， dp[1] 是偷的最大金钱

class Solution {
public:
    int rob(TreeNode* root) {
        // 左右的孩子节点，递归返回 dp 数组
       vector<int> ret = reverseTraversal(root);
       return max(ret[0], ret[1]);
    }

    vector<int> reverseTraversal(TreeNode* root) {
        // 0 代表没有偷， 1 代表偷了
        vector<int> dp(2, 0);
        if (root == nullptr) return dp;

        vector<int> left = reverseTraversal(root->left);
        vector<int> right = reverseTraversal(root->right);

        dp[1] = left[0] + right[0] + root->val;
        dp[0] = max(left[0], left[1]) + max(right[0], right[1]); // 这里要注意，取最大的，不一定要偷左右孩子
        return dp;
    }
};

5.8 买卖股票的最佳时机

LeetCode 121

这道题简单，但是我们抛砖引玉一下，用 dp 的方法来计算这一类的问题

这个 dp 数组的定义比较抽象，主要是为了能够包含所有的状态（例如定义第 i 天卖出的收益，那么什么都不做，怎么用第 i 天卖出这个定义表示呢？）

dp[i][0] 表示第 i 天不持有这个股票的最大现金，而 dp[i][1]表示持有下的最大现金，注意这里是持有，不一定是当天进行了买卖
初始化：dp[0][0] = 0, dp[0][1] = - price[0]
递推公式：

dp[i][0] = dp[i - 1][0] 表示今天不执行任何操作
dp[i][0] = dp[i - 1][1] + price[i] 表示把股票卖了
dp[i][1] = dp[i - 1][0]- price[i] 表示第 i 天买入了这个股票（本题只买卖一次，所以必须等于 - price[i]）
dp[i][1] = dp[i - 1][1] 不执行任何操作
上述分别取最大值就是递推公式

递归顺序：常规从前到后即可

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        vector<vector<int>> dp(prices.size(), vector<int>(2, 0));
        dp[0][1] = -prices[0];
        for (int i = 1; i < prices.size(); i++) {
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            dp[i][1] = max(dp[i - 1][1], - prices[i]); // 只允许买入一次
        }
        return dp[prices.size() - 1][0];
    }
};

5.9 最长递增子序列

LeetCode 300

这题目是很经典的 dp 题目，难点在怎么定义 dp 数组

很多题目都用结尾作为 dp 数组的定义，实际原因是，这类题型只有末尾才能够构成严格递推关系，因为很多时候长度不固定的，定义开头无法确定递推；但是由于前 n 个的最优解一定包含在前 n+1 当中

定义：以 num[i] 结尾的最长子序列的长度，因为计算递增一定要有一个末尾固定才好算
递推公式：if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1; ，每一个都要把前面的数字的全部统计一次
初始化：序列的长度肯定至少都是 1，剩下的取最大值就可以更新
遍历顺序：根据公式肯定是从前向后

这是这道题的 dp 写法，复杂度 $O(n^2)$ 这道题实际上还有个二分优化的方法，不过日后再写吧

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        // dp
        vector<int> dp(nums.size(), 1); // 全部初始化为1
        int ret = 1;
        for (int i = 1; i < nums.size(); i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j])
                    // 从前面取一个末尾小于本体，然后 + 1
                    dp[i] = max(dp[i], dp[j] + 1);
            }
            ret = max(ret, dp[i]);
        }
        return ret;
    }
};

5.10 最长重复子数组

LeetCode 718

这里能够总结出一个经验，就是把无效的状态全部都塞进 0 的位置，可以省去很多麻烦的初始化步骤

例如本题目把 dp[i][j] 定义为下标 [i - 1] [j - 1] 的数组的最长重复子数组，可以省去初始化部分

class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size(), m = nums2.size();
        // 初始化注意要 + 1
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
        int ret = 0;
        // 从 1 开始，不用考虑边界，同时覆盖了所有可能的解
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    ret = max(ret, dp[i][j]);
                }
            }
        }
        return ret;
    }
};

5.11 编辑距离

LeetCode 72

编辑距离，这是一维优化后的解法，详细可以参考开头的内容

class Solution {
public:
    int minDistance(string word1, string word2) {
        // 编辑距离 一维优化
        // 尤其注意在横纵的初始值都不是 0 的时候，纵向初始值在 1 维 dp 每一轮都要修正
        int m = word1.size();
        int n = word2.size();
        vector<int> dp(n + 1, 0);
        for (int j = 0; j <= n; j++) dp[j] = j;
        for (int i = 1; i <= m; i++) {
            int pre = dp[0]; // 对于本轮来说是 dp[1 - 1][j - 1];
            dp[0] = i;  // dp[0] 需要随着 i 轮次进行更新，为下一轮的 pre 准备
            for (int j = 1; j <= n; j++) {
                int tmp = dp[j]; // 保存下一回的 dp[i - 1][j - 1];
                if (word1[i - 1] == word2[j - 1]) {
                    dp[j] = pre; // 来自上一回的 dp[i - 1][j - 1]
                } else {
                    dp[j] = min({dp[j - 1], dp[j], pre}) + 1;
                }
                pre = tmp;
                // cout << dp[j] << ' ';
            }
            // cout << endl;
        }
        return dp[n];
    }
};

5.12 最长回文子序列

LeetCode 516

看到子序列基本上就是 dp 的解法了

具体的状态转移可以参见开头写的子序列问题，这是 LeetCode 的官方解法

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int n = s.length();
        vector<vector<int>> dp(n, vector<int>(n));
        for (int i = n - 1; i >= 0; i--) {
            dp[i][i] = 1;
            for (int j = i + 1; j < n; j++) {
                if (s[i] == s[j]) {
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                } else {
                    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[0][n - 1];
    }
};

6 总结

这类题目的难点在于是不是能够合理的猜想出一个可行的 dp 数组定义，这很依赖经验

另外，如果有了一个 dp 数组定义的想法了，我的建议是写一个 一般一点的例子 来列出整个 dp 数组

我的意思是，相比于对着逻辑进行直接推到状态转移的关系，有时候瞪眼法看看数组找规律也许很有效（也就是猜一个转移过程来证明一下，对于复杂一点的题目可能会好写一点）

快速跳转

站点说明

目录架构

最近更新

目录架构

最近更新

目录架构

最近更新

目录架构

最近更新

动态规划

动态规划

1 解题步骤

1.1 什么时候用

2 背包问题

2.1 零一背包（二维数组）

2.2 零一背包（滚动数组）

2.3 完全背包

2.4 完全背包的排列组合

3 股票问题

4 子序列问题

4.1 LCS 最长子序列

4.2 编辑距离

4.3 回文串

5 经典题目

5.1 爬楼梯

5.2 不同的二叉搜索树

5.3 分割等和子集

5.4 目标和

5.5 完全平方数

5.6 单词拆分

5.7 打家劫舍 III

5.8 买卖股票的最佳时机

5.9 最长递增子序列

5.10 最长重复子数组

5.11 编辑距离

5.12 最长回文子序列

6 总结

动态规划

动态规划

1 解题步骤

1.1 什么时候用

2 背包问题

2.1 零一背包 （二维数组）

2.2 零一背包（滚动数组）

2.3 完全背包

2.4 完全背包的排列组合

3 股票问题

4 子序列问题

4.1 LCS 最长子序列

4.2 编辑距离

4.3 回文串

5 经典题目

5.1 爬楼梯

5.2 不同的二叉搜索树

5.3 分割等和子集

5.4 目标和

5.5 完全平方数

5.6 单词拆分

5.7 打家劫舍 III

5.8 买卖股票的最佳时机

5.9 最长递增子序列

5.10 最长重复子数组

5.11 编辑距离

5.12 最长回文子序列

6 总结

2.1 零一背包（二维数组）