【代码随想录】41

Miyi

2023-10-24

算法

2023年10月24日 - 动态规划8

139. 单词拆分

完全背包的思路解决

 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 i = 1; i <= s.size(); i++) {   // 遍历背包
             for (int j = 0; j < i; j++) {       // 遍历物品
                 string word = s.substr(j, i - j); //substr(起始位置，截取的个数)
                 if (wordSet.find(word) != wordSet.end() && dp[j]) {
                     dp[i] = true;
                 }
             }
         }
         return dp[s.size()];
     }
 };

背包问题总结

递推公式

纯完全背包类问题，先遍历物品还是先遍历背包可以颠倒的

问能否装满背包（或最多装多少）

递推公式 dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);

如果求装满背包有多少种方法，就要区分求组合数还是排列数

如果求组合数就是外层for循环遍历物品，内层for遍历背包。这样子就不会重复

如果求排列数就是外层for遍历背包，内层for循环遍历物品。

内层从大到小还是从小到大取决于是否可以重复取

递推公式 dp[j] += dp[j - nums[i]]

问背包装满最大价值

递推公式 dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

动态规划：474.一和零

问装满背包所有物品的最小个数

递推公式 dp[j] = min(dp[j - coins[i]] + 1, dp[j]);

遍历顺序

01背包

在动态规划：关于01背包问题，你该了解这些！ (opens new window)中我们讲解二维dp数组01背包先遍历物品还是先遍历背包都是可以的，且第二层for循环是从小到大遍历。

和动态规划：关于01背包问题，你该了解这些！（滚动数组） (opens new window)中，我们讲解一维dp数组01背包只能先遍历物品再遍历背包容量，且第二层for循环是从大到小遍历。

完全背包

在动态规划：关于完全背包，你该了解这些！ (opens new window)中，讲解了纯完全背包的一维dp数组实现，先遍历物品还是先遍历背包都是可以的，且第二层for循环是从小到大遍历。

如果求组合数就是外层for循环遍历物品，内层for遍历背包。

如果求排列数就是外层for遍历背包，内层for循环遍历物品。