Cybay
0%

动态规划

发表于 更新于 分类于 Valine：
动态规划

背包问题

0-1背包

模型

有n件物品与一个承重w的背包，第i件物品的重量是weight[i]，价值是value[i]，每件物品只能用一次，求装入物品价值总和的最大值。

二维数组dp

dp数组含义

dp[i] [j] 表示从物品0-i中取物品，放入承重为j的背包中的最大价值。

递推公式
1
dp[i][j] = max(dp[i - 1][j]/*不装入物品i*/, dp[i - 1][j - weight[i]] + value[i]/*装入i*/);
初始化
1
2
3
4
vector<vector<int>> dp(n, vector<int>(w + 1, 0));
//放入第一个物品
for(int j = weight[0]; j < w; ++j)
    dp[0][j] = value[0];
实现
1
2
3
4
for(int i = 1; i < n; ++i)    //遍历物品
    for(int j = 0; j <= w; ++j)   //遍历背包承重
        if(j - weight[i] >= 0)
        	dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

滚动数组dp

dp数组含义

dp[i]表示承重为i的背包可装入的最大价值

递推公式
1
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
初始化
1
vector<int> dp(n + 1, 0);
实现
1
2
3
for(int i = 0; i < n; ++i)
    for(int j = w; j >= weight; --j)  //倒序遍历，防止同一物品多次放入背包
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
应用
目标和Target Sum
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int findTargetSumWays(vector<int>& nums, int target) {
        
        int sum = 0;
        for(int k : nums)
            sum += k;
        if(abs(target) > sum) return 0;
        int wt = sum + target;
        if(wt % 2) return 0;
        wt /= 2;
        vector<int> dp(wt + 1, 0);
        dp[0] = 1; 
        for(int i = 0; i < nums.size(); ++i)
            for(int j = wt; j >= nums[i]; --j)
            {
                dp[j] += dp[j - nums[i]];
            }
        return dp[wt];
    }
一和零Ones and Zeroes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int findMaxForm(vector<string>& strs, int m, int n) {
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        for(int i = 0; i < strs.size(); ++i)
        {
            int oneNums(0), zeroNums(0);
            for(char c : strs[i])
                if(c == '0') ++zeroNums;
                else ++oneNums;
            for(int j = m; j >= zeroNums; --j)
                for(int k = n; k >= oneNums; --k)
                    dp[j][k] = std::max(dp[j][k],
                    dp[j - zeroNums][k - oneNums] + 1);
        }
        return dp[m][n];
    }

完全背包

物品可以重复使用。

实现
1
2
3
for(int i = 0; i < n; ++i)
    for(int j = weight[i]; j <= weight; ++j)  //正序遍历
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
应用
零钱兑换II[Coin Change 2]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
//求组合数，先遍历物品
//求排列数，先遍历背包容量

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<int> dp(amount + 1, 0);
        dp[0] = 1;
        for(size_t i = 0; i < coins.size(); ++i) //求组合数
            for(int j = coins[i]; j <= amount; ++j)
                dp[j] += dp[j - coins[i]];
        return dp[amount];
    }
};
组合总和 ⅣCombination IV
1
2
3
4
5
6
7
8
9
10
11
12
13
14
//本题求排列数
class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        vector<int> dp(target + 1, 0);
        dp[0] = 1;
        for(int j = 0; j <= target; ++j)
            for(size_t i = 0; i < nums.size(); ++i)
                if(j - nums[i] >= 0 && 
                dp[j] < INT_MAX - dp[j - nums[i]]) dp[j] += dp[j - nums[i]];
        return dp[target];
    }
};

子序列

出现个数[Distinct Subsequences]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int numDistinct(string s, string t) {
        vector<vector<uint64_t>> dp(s.size() + 1, vector<uint64_t>(t.size() + 1));
        for(int i = 0; i <= s.size(); ++i) dp[i][0] = 1;
        for(int i = 1; i <= s.size(); ++i)
            for(int j = 1; j <= t.size(); ++j)
            {
                if(s[i - 1] == t[j - 1])
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                else 
                    dp[i][j] = dp[i - 1][j];
            }
        return dp[s.size()][t.size()];
    }
};

编辑距离

两个字符串的删除操作[Delete Operation for Two Strings]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int minDistance(string word1, string word2) {
        vector<vector<int>> dp(word1.length() + 1, vector<int>(word2.length() + 1));
        for(size_t i = 1; i <= word1.length(); ++i)
            dp[i][0] = i;
        for(size_t j = 1; j <= word2.length(); ++j)
            dp[0][j] = j;
        for(string::size_type i = 1; i <= word1.size(); ++i)
            for(decltype(i) j = 1; j <= word2.length(); ++j)
            {
                if(word1[i - 1] == word2[j - 1])
                    dp[i][j] = dp[i - 1][j - 1];
                else
                    dp[i][j] = std::min({dp[i - 1][j] + 1, 
                    dp[i - 1][j - 1] + 2, dp[i][j - 1] + 1}); 
            }
        return dp[word1.size()][word2.size()];
    }
};