代码随想录算法训练营第46天 | 139.单词拆分, 多重背包, 背包问题总结

139.单词拆分

代码随想录链接

题目

LeetCode-139.单词拆分

给定一个非空字符串和一个包含非空单词的数组, 判断非空字符串能否由数组中的单词组成. 一个单词可以使用多次, 没有重复的单词.

题目分析

转化为背包问题, 单词就是物品, 字符串就是背包, 因为同一个单词可以多次取, 所以是完全背包问题.

动态规划五部曲:

• 确定dp数组及下标的含义

  \(dp[j]\), 字符串长度为j时, 能否由数组内单词组成.

• 确定递推公式

  当区间字符串\([i, j]\)区间的子字符串出现在数组内的单词且\(dp[i]\)为true时, \(dp[j]\)也为true.

• dp数组的初始化

  dp[0] = true, 仅用于推导公式

• 遍历顺序

  用单词拼接字符串是需要注重顺序的, 所以需要先遍历背包, 再遍历物品

  for (int j = 1; j <= s.size(); j++)
      for (int i = 0; i < j; i++) {
          string word = s.substr(i, j - i);
          if (wordSet.find(word) != wordSet.end() && dp[i])
              dp[j] = true;
          }

• 举例推导

题解

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
        vector<bool> dp(s.size() + 1, false);
        dp[0] = true;
        for (int j = 1; j <= s.size(); j++)
            for (int i = 0; i < j; i++) {
                string word = s.substr(i, j - i);
                if (wordSet.find(word) != wordSet.end() && dp[i])
                    dp[j] = true;
            }  
        return dp[s.size()];
    }
};

多重背包

多重背包就是在0-1背包的基础上, 同样的一件物品可能有不同的数量限制.

比如物品可能有:

	重量	价值	数量
物品0	1	15	2
物品1	3	20	3
物品2	4	30	2

解决方法也很简单, 将相同的物品展开为一个一个"不同"的物品, 然后当做0-1背包问题处理即可.

背包问题总结

动态规划五部曲:

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

dp数组

基本上题目求得是什么, dp数组的值就代表什么.

例如, 求最多能装多少, 那么dp数组的值就是不同容量时最多能装多少; 求有几种方法, dp数组的值就代表几种方法; 求最大价值, 那么dp数组就代表对应容量的最大价值.

递推公式

最多能装多少

问最多能装多少, 就把物品看做价值和重量相同的物品.

递推公式为:

\[dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]\]

例题:

• 416.分割等和子集
• 1049.最后一块石头的重量

几种方法

求几种方法时, 一般是将背包容量小于当前位置的数值求和得到:

\[dp[j] += dp[j - nums[i]]\]

例题:

• 494.目标和
• 518.零钱兑换II
• 377.组合总和IV
• 70.爬楼梯(进阶)

背包的最大价值

由前一个状态(没有装当前物品的背包状态), 和当前背包容量的状态得到.

\[dp[j] = max(dp[j], dp[j - weight[i]] + values[i])\]

例题:

• 474.一和零

装满背包最少物品数

由上一个状态(没装当前物品)的个数和当前状态得到.

\[dp[j] = min(dp[j], dp[j - coins[i]] + 1)\]

例题:

• 322.零钱兑换
• 279.完全平方数

遍历顺序

0-1背包

二维dp数组:

// weight数组的大小 就是物品个数
for(int i = 1; i < weight.size(); i++) { // 遍历物品
    for(int j = 0; j <= bagweight; j++) { // 遍历背包容量
        if (j < weight[i]) dp[i][j] = dp[i - 1][j];
        else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

    }
}

// weight数组的大小 就是物品个数
for(int j = 0; j <= bagweight; j++) { // 遍历背包容量
    for(int i = 1; i < weight.size(); i++) { // 遍历物品
        if (j < weight[i]) dp[i][j] = dp[i - 1][j];
        else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
    }
}

一维dp数组:

只能外层循环遍历物品, 内层(倒序)遍历背包容量

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

完全背包

纯完全背包(顺序可有可无):

注意两个循环都是索引从小到大遍历的

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

求组合数时:

外层for循环遍历物品, 内层for循环遍历背包.

例题:

• 518.零钱兑换II

求排列数:

外层for循环遍历背包, 内层for循环遍历物品.

例题:

• 377.组合总和IV
• 70.爬楼梯(进阶)