动态规划总结

Miyako2025-09-092026-05-03

解题步骤

确定dp数组的含义
确定递推公式
初始化dp数组
确定遍历顺序
举例推导dp数组

背包问题

0-1背包

有n件物品，最多能背重量为w的背包，其中第i件物品的重量为weight[i]，价值为value[i],每一个物品只能用一次，问如何装价值总和最大。

暴力可以用回溯法求解，每一个物品有取和不取两个状态，时间复杂度为 $O(2^n)$。

#include<iostream>
#include<vector>

using namespace std;

int main(){ //二维数组实现0-1背包
    int n,bagweight;
    cin>>n>>bagweight;
    vector<int> weight(n);
    vector<int> value(n);
    for(int i=0;i<n;i++){
        cin>>weight[i];
    }
    for(int i=0;i<n;i++){
        cin>>value[i];
    }
    vector<vector<int>> dp(n,vector<int>(bagweight+1,0));
    for(int i=0;i<=bagweight;i++){
        if(i>=weight[0]){
            dp[0][i] = value[0];
        }
    }
    for(int i=1;i<n;i++){ //遍历物品
        for(int j=0;j<=bagweight;j++){
            if(j>=weight[i]){
                dp[i][j] = max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i]);
            }
            else{
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    cout<<dp[n-1][bagweight]<<endl;
}

#include<iostream>
#include<vector>

using namespace std;

int main(){ //一维数组
    int n,bagweight;
    cin>>n>>bagweight;
    vector<int> weight(n);
    vector<int> value(n);
    for(int i=0;i<n;i++){
        cin>>weight[i];
    }
    for(int i=0;i<n;i++){
        cin>>value[i];
    }
    vector<int> dp(bagweight+1,0); //dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]
    for(int i=0;i<n;i++){ //遍历物品
        for(int j=bagweight;j>=weight[i];j--){
                dp[j] = max(dp[j],dp[j-weight[i]]+value[i]);
            }
        }
    cout<<dp[bagweight]<<endl;
}

求背包是否可以装满

leetcode 416.分割等和子集，对于数字，其value=weight，判断其是否可以装满，只需要判断dp[target]是否等于target即可。

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;
        for(int num:nums){
            sum+=num;
        }
        if(sum%2!=0) return false;
        int bagweight = sum/2;
        vector<int> dp(bagweight+1,0); //dp[j] 表示： 容量（所能装的重量）为j的背包，所背的物品价值最大可以为dp[j]
        for(int i=0;i<nums.size();i++){
            for(int j = bagweight;j>=nums[i];j--){
                dp[j] = max(dp[j],dp[j-nums[i]]+nums[i]);
            }
        }
        return dp[bagweight]==bagweight;
    }
};

尽量装满背包总共有多重

leetcode 1049.最后一块石头的重量II,希望能够得到最小的石头，只需要两堆重量接近的石头相撞，因此可以用背包解决，装满target容量的背包，最多能凑到多重，然后两堆石头相减即可。

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int sum = 0;
        for(int num:stones){
            sum+=num;
        }
        int target = sum/2; //尽量分成一样两堆
        vector<int> dp(target+1); //尽量凑满target的背包，能够装多少
        for(int i=0;i<stones.size();i++){
            for(int j=target;j>=stones[i];j--){
                dp[j] = max(dp[j],dp[j-stones[i]]+stones[i]);
            }
        }
        return sum-2*dp[target];
    }
};

装满背包有多少种方法

leetcode 494.目标和,题目中集合数字可以取正取负，如果需要得到target，可以算出取正数的总和left = (target + sum)/2,因此题目转化为装满容量为left，总共有几种方法。

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum = 0;
        for(int num:nums){
            sum+=num;
        }
        int left = (sum+target)/2;
        if((sum+target)%2!=0) return 0;
        if(left <0) return 0;
        vector<int> dp(left+1,0); //dp[j]表示装满容量为j的背包有dp[j]种方法
        dp[0] = 1; //需要初始化
        for(int i=0;i<nums.size();i++){
            for(int j = left;j>=nums[i];j--){
                dp[j]+= dp[j-nums[i]];  //dp[5]的方法由,当已经选了nums[i]时，剩下的方法加起来
            }
        }
        return dp[left];
    }
};

装满背包用多少个物品

leetcode 474.一和零，m和n为背包容量，物品有两个维度，dp数组改为装满该容量的物品数量，取该物品时，dp则为减去物品容量后加1。

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<vector<int>> dp(m+1,vector<int>(n+1,0)); //dp[i][j]表示最多有i个0，j个1，子集长度
        for(int i=0;i<strs.size();i++){
            int one =0;
            int zero = 0;
            for(char c:strs[i]){
                if(c=='0') zero++;
                else one++;
            }
            for(int j=m;j>=zero;j--){
                for(int k=n;k>=one;k--){
                    dp[j][k] = max(dp[j-zero][k-one]+1,dp[j][k]);
                }
            }
        }
        return dp[m][n];
    }
};

完全背包

相对于0-1背包，遍历背包的时候正序遍历即可，对于纯完全背包问题，遍历顺序可以交换。

#include<iostream>
#include<vector>

using namespace std;

int main(){
    int n,bagweight;
    cin>>n>>bagweight;
    vector<int> weight(n);
    vector<int> value(n);
    for(int i=0;i<n;i++){
        cin>>weight[i]>>value[i];
    }
    vector<int> dp(bagweight+1,0);
    for(int i=0;i<n;i++){
        for(int j=weight[i];j<=bagweight;j++){
            dp[j] = max(dp[j],dp[j-weight[i]]+value[i]);
        }
    }
    cout<<dp[bagweight]<<endl;
}

装满背包有多少种方法（组合数）

leetcode 518.零钱兑换II,类似于目标和，把遍历改成完全背包即可。

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<int> dp(amount+1,0); //dp[j]表示装满容量为j，有dp[j]种方法
        dp[0] = 1;
        for(int i=0;i<coins.size();i++){ //遍历物品
            for(int j=coins[i];j<=amount;j++){
                dp[j] += dp[j-coins[i]];
            }
        }
        return dp[amount];
    }
};

装满背包有多少种方法(排列数)

leetcode 377.组合总和 Ⅳ,求的是排列数，只需要把遍历顺序改一下即可，先遍历背包再遍历物品。

如果先遍历物品再遍历背包，在物品先固定的情况下，遍历完一遍后只有物品1，等到物品2的时候，只能在前一轮只有物品1的情况下添加，这样就不会出现{物品2，物品1}的情况。

如果先遍历背包再遍历物品，在背包固定的情况下，遍历完后可能有物品1和物品2，当背包变大进入下一轮，物品又从物品1开始进行添加，所以会出现{物品2，物品1}的情况，对应排列。

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        vector<int> dp(target + 1, 0);
        dp[0] = 1;
        for (int i = 0; i <= target; i++) { // 遍历背包
            for (int j = 0; j < nums.size(); j++) { // 遍历物品
                if (i - nums[j] >= 0 && dp[i] < INT_MAX - dp[i - nums[j]]) {
                    dp[i] += dp[i - nums[j]];
                }
            }
        }
        return dp[target];
    }
};

装满背包最少的物品件数

leetcode 322.零钱兑换,初始化需要注意，当dp[j-coins[i]]为INT_MAX说明这个amount不能被凑到。

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount+1,INT_MAX); //dp[j]表示凑足j最少的金币数量
        dp[0] = 0;
        for(int i=0;i<coins.size();i++){
            for(int j=coins[i];j<=amount;j++){
                if(dp[j-coins[i]]!=INT_MAX){
                    dp[j] = min(dp[j],dp[j-coins[i]]+1);
                }
            }
        }
        if(dp[amount]==INT_MAX) return -1;
        return dp[amount];
    }
};

多重背包

可以将其看作是0-1背包进行运算，即物品i有n件，就把他拆成n个物品，然后价值和数量不变，这样就转为了0-1背包问题。

#include<iostream>
#include<vector>
 
using namespace std;
 
int main(){
    int bag,n;
    cin>>bag>>n;
    vector<int> weight(n,0);
    vector<int> value(n,0);
    vector<int> cnt(n,0);
    for(int i=0;i<3;i++){
        for(int j=0;j<n;j++){
            if(i==0) cin>>weight[j];
            if(i==1) cin>>value[j];
            if(i==2) cin>>cnt[j];
        }
    }
    vector<int> new_weight;
    vector<int> new_value;
    for(int i=0;i<cnt.size();i++){
        while(cnt[i]--){
            new_weight.push_back(weight[i]);
            new_value.push_back(value[i]);
        }
    }
    vector<int> dp(bag+1,0);
    for(int i=0;i<new_weight.size();i++){
        for(int j=bag;j>=new_weight[i];j--){
            dp[j] = max(dp[j],dp[j-new_weight[i]]+new_value[i]);
        }
    }
    cout<<dp[bag]<<endl;
    return 0;
}

打家劫舍

考虑dp的定义为dp[i]：包括i以内的房屋，最多可以偷窃的金额为dp[i];

然后递推公式可以得：dp[i] = max(dp[i-1],dp[i-2]+nums[i]);

class Solution {
public:
    int rob(vector<int>& nums) {
        vector<int> dp(nums.size(),0); //dp[i]表示考虑0-i，最大的钱
        dp[0] = nums[0]; //初始化前两个房子
        if(nums.size()==1) return nums[0];
        dp[1] = max(nums[0],nums[1]);
        for(int i=2;i<nums.size();i++){
            dp[i] = max(dp[i-1],dp[i-2]+nums[i]);
        }
        return dp[nums.size()-1];
    }
};

如果是二叉树结构，则对每一个节点进行判断偷不偷，随后取最大值。
```cpp
class Solution {
private:
    vector<int> traversal(TreeNode* node){
        if(node==nullptr) return {0,0};
        vector<int> left = traversal(node->left);
        vector<int> right = traversal(node->right);
        int value0 = left[1]+right[1]+node->val;//偷该节点
        int value1 = max(left[1],left[0])+max(right[0],right[1]); //不偷该节点,左右两个节点取最大的
        return {value0,value1};
    }
public:
    int rob(TreeNode* root) {
        vector<int> result = traversal(root);
        return max(result[0],result[1]);
    }
};

股票问题

leetcode 122. 买卖股票的最佳时机 II

dp数组的定义：dp[i][0]表示第i天持有股票所得最多现金，dp[i][1]表示第i天不持有(并不代表买入)股票所得最多现金。

递推公式：第i天持有股票即dp[i][0]由两个状态推来：第i-1天持有股票即dp[i-1][0];第i天买入股票，所得现金减去购入股票的现金即:-prices[i]。

所以

dp[i][0] = max(dp[i-1][0],dp[i-1][1]-prices[i]);

dp[i][1] = max(dp[i-1][0]+prices[i],dp[i-1][1]);

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        vector<vector<int>> dp(prices.size(),vector<int>(2,0));
        dp[0][0] = -prices[0];
        dp[0][1] = 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],dp[i-1][0]+prices[i]);
        }
        return dp[prices.size()-1][1];
    }
};

leetcode 123.买卖股票的最佳时机III

这个题目最多只能完成两笔交易，那dp的定义需要略微修改。改为四个状态，第一次持有股票，第一次不持有股票，第二次持有股票，第二次不持有股票。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.size()==0) return 0;
        vector<vector<int>> dp(prices.size(),vector<int>(4,0));
        dp[0][0] = -prices[0];
        dp[0][1] = -prices[0];
        dp[0][2] = 0;
        dp[0][3] = 0;
        for(int i =1;i<prices.size();i++){
            dp[i][0] = max(dp[i-1][0],-prices[i]);
            dp[i][1] = max(dp[i-1][2]-prices[i],dp[i-1][1]);
            dp[i][2] = max(dp[i-1][0]+prices[i],dp[i-1][2]);
            dp[i][3] = max(dp[i-1][1]+prices[i],dp[i-1][3]);
        }
        return dp[prices.size()-1][3];
    }
};

leetcode 309.最佳买卖股票时机含冷冻期

包含一个购买后的冷冻期，可以分为四个状态: 买入股票状态dp[i][0],保持卖出股票状态dp[i][1],今天卖出股票状态dp[i][2],冷冻期状态dp[i][3].

dp[i][0] = max(max(dp[i-1][3]-prices[i],dp[i-1][1]-prices[i]),dp[i-1][0]); //买入状态由冷静期，昨天买入，卖出状态推得
dp[i][1] = max(dp[i-1][1],dp[i-1][3]); //卖出状态由前一天卖出状态和冷冻期状态推出
dp[i][2] = dp[i-1][0]+prices[i]; //今天卖出状态由买入状态推得
dp[i][3] = dp[i-1][2]; //冷冻期由今天卖出推得

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if (n == 0) return 0;
        vector<vector<int>> dp(n, vector<int>(4, 0));
        dp[0][0] -= prices[0]; // 持股票
        for (int i = 1; i < n; i++) {
            dp[i][0] = max(dp[i - 1][0], max(dp[i - 1][3] - prices[i], dp[i - 1][1] - prices[i]));
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][3]);
            dp[i][2] = dp[i - 1][0] + prices[i];
            dp[i][3] = dp[i - 1][2];
        }
        return max(dp[n - 1][3], max(dp[n - 1][1], dp[n - 1][2]));
    }
};

子序列问题

leetcode 300.最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

他的dp定义为:dp[i]表示i之前包括i以nums[i]结尾的最长递增子序列长度。

递推公式为:

1
2
3

if(nums[i]>nums[j]){
    dp[i] = max(dp[i],dp[j]+1); //j为0到i-1各个位置为结尾的最长递增子序列长度
}//max用于取最大的dp[j]+1

初始化dp[0] = 1,遍历为两层。

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> dp(nums.size(),1);
        int result = 0;
        for(int i=1;i<nums.size();i++){
            for(int j=0;j<i;j++){
                if(nums[i]>nums[j]){
                    dp[i] = max(dp[i],dp[j]+1);
                }
            }
            result = max(result,dp[i]);
        }
        return result;
    }
};

leetcode 674. 最长连续递增序列

dp[i]的定义为以下标i为结尾的连续递增序列长度为dp[i]。

递推公式为:

1
2
3

if(nums[i]>nums[i-1]){
    dp[i] = dp[i-1]+1;
}

class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) {
        vector<int> dp(nums.size(),1);
        int result =1;
        for(int i=1;i<nums.size();i++){
            if(nums[i]>nums[i-1]){
                dp[i] = dp[i-1]+1;
            }
            result= max(result,dp[i]);
        }
        return result;
    }
};

leetcode 718. 最长重复子数组

给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的连续子序列的长度。

dp[i][j]：以下标i-1为结尾的A和以j-1为结尾的B，最长重复子数组长度为dp[i][j].

//递推公式
if(nums1[i-1]==nums2[j-1]){
    dp[i][j] = dp[i-1][j-1]+1;
}

class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        vector<vector<int>> dp(nums1.size()+1,vector<int>(nums2.size()+1,0));
        int result = 0;
        for(int i=1;i<=nums1.size();i++){
            for(int j=1;j<=nums2.size();j++){
                if(nums1[i-1]==nums2[j-1]){
                    dp[i][j] = dp[i-1][j-1]+1;
                }
                result = max(result,dp[i][j]);
            }
        }
        return result;
    }
};

leetcode 1143.最长公共子序列

相对于题718，差别在于不是连续的而是子序列。

dp[i][j]表示为长度为[0,i-1]的字符串text1与长度为[0,j-1]的字符串text2的最长公共子序列为dp[i][j]

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

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        vector<vector<int>> dp(text1.size()+1,vector<int>(text2.size()+1,0));
        
        for(int i=1;i<=text1.size();i++){
            for(int j=1;j<=text2.size();j++){
                if(text1[i-1]==text2[j-1]){
                    dp[i][j] = dp[i-1][j-1] + 1;
                }
                else{
                    dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        return dp[text1.size()][text2.size()];
    }
};

leetcode 53. 最大子序和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

输入: [-2,1,-3,4,-1,2,1,-5,4] 连续子数组 [4,-1,2,1] 的和最大，为 6。

dp[i]表示以nums[i]为结尾的最大连续子序列的和为dp[i]

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        if(nums.size()==1) return nums[0];
        vector<int> dp(nums.size());
        dp[0] = nums[0];
        int result = dp[0];
        for(int i= 1;i<nums.size();i++){
            if(dp[i-1]<0){
                dp[i] = nums[i]; //前面的小于0重新开始
            }
            else{
                dp[i] = dp[i-1] + nums[i];
            }
            result = max(result,dp[i]);
        }
        return result;
    }
};