139.單詞拆分

可以理解為一道 完全背包 + 排列 的題，dp數組定義和遞推公式部分腦子需要轉個彎

1、DP數組定義：一維滾動數組vector<bool>。dp[j]表示字符串s的[0, j]子串是否能夠匹配。

2、DP數組初始化：dp[0]初始化為true，其余元素初始化為false，題目中沒有對dp[0]做出限制，將其設置為true是由于遞推公式需求。

3、遞推公式：本題與其說是遞推公式，不如將其理解為“如果前面部分已經符合了，再看看當前是否還能符合”。

4、遍歷順序：按 完全背包 + 排列 的順序遍歷

bool wordBreak(string s, vector<string>& wordDict) {// dp[j]表示字符串s的[0, j]子串是否能夠匹配vector<bool> dp(s.size() + 1, false);// 空字符串初始化為truedp[0] = true;for (int j = 0; j <= s.size(); ++j) {for (int i = 0; i < wordDict.size(); ++i) {int l = wordDict[i].size();// 條件1：長度足夠// 條件2：前 j - l 個字符能夠匹配（前面都不能匹配那當前也沒有匹配的必要）// 條件3：前 j 還沒匹配（匹配好了就沒有修改的必要了）if (j - l >= 0 && dp[j - l] && !dp[j]) { dp[j] = true;// 逐個匹配字符，如果全部匹配則將dp[j]設置為truefor (int k = 0; k < l; ++k) {if (s[j - l + k] != wordDict[i][k]) {dp[j] = false;break;}}}}}return dp[s.size()];
}

---

?多重背包（卡碼網56.攜帶礦石資源）

多重背包能夠當成0-1背包來理解：

多重背包中，每個物品都有其使用次數限制。假設物品 i 能使用 nums[i] 次，將物品 i 拆成 nums[i] 個物品，問題就轉換為了0-1背包問題

寫起來時整體就是0-1背包多加一次遍歷nums[i]的循環，但這層循環具體加在哪里是會有不小的性能差異的：

最直觀的寫法：直接插在遍歷 i 之后，相當于把物品i全部拆開一個個遍歷。這樣寫容易超時：

// 第一行包含兩個整數 C 和 N，分別表示宇航艙的容量和礦石的種類數量。 
// 接下來的三行，每行包含 N 個正整數。具體如下：
// 第二行包含 N 個整數，表示 N 種礦石的重量。
// 第三行包含 N 個整數，表示 N 種礦石的價格。
// 第四行包含 N 個整數，表示 N 種礦石的可用數量上限。
// 輸出一個整數，代表獲取的最大價值。
int bag(int begWeight, int n, vector<int> value, vector<int> weight, vector<int> nums) {vector<int> dp(begWeight + 1, 0);for (int i = 0; i < n; ++i) {// 把物品i全都散開一個個加for (int k = 0; k < nums[i]; ++k) {for (int j = begWeight; j >= weight[i]; --j) {dp[j] = std::max(dp[j], dp[j - weight[i]] + value[i]);}}}return dp[begWeight];
}

更好的寫法：將這層循環插在最內層，判斷如果加入物品i，是加1個、2個還是更多個

int bag(int begWeight, int n, vector<int> value, vector<int> weight, vector<int> nums) {vector<int> dp(begWeight + 1, 0);for (int i = 0; i < n; ++i) {for (int j = begWeight; j >= weight[i]; --j) {// 判斷物品i是加1個、2個、還是3個……for (int k = 1; k <= nums[i] && (j - k * weight[i]) >= 0; ++k) {dp[j] = std::max(dp[j], dp[j - k * weight[i]] + k * value[i]);}}}return dp[begWeight];
}