前言
更詳細的在大佬的代碼隨想錄 (programmercarl.com)
本系列僅是簡潔版筆記，為了之后方便觀看
完全背包
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]);}}?零錢兌換II
. - 力扣（LeetCode）
因為純完全背包不在乎有沒有順序，有順序也行沒有順序也行，但是這個題目的要求是沒有順序，求組合數，所以就要考慮for循環先后順序調換有沒有影響了
組合情況：先把1加入計算，然后再把5加入計算，得到的方法數量只有{1, 5}這種情況。而不會出現{5, 1}的情況
for (int i = 0; i < coins.size(); i++) { // 遍歷物品for (int j = coins[i]; j <= amount; j++) { // 遍歷背包容量dp[j] += dp[j - coins[i]];}
}排列數情況：背包容量的每一個值，都是經過 1 和 5 的計算，包含了{1, 5} 和 {5, 1}兩種情況。?
for (int j = 0; j <= amount; j++) { // 遍歷背包容量for (int i = 0; i < coins.size(); i++) { // 遍歷物品if (j - coins[i] >= 0) dp[j] += dp[j - coins[i]];}
}組合總和IV
. - 力扣（LeetCode）
if 語句的作用
確保在執行狀態轉移時不會訪問不合法的索引，防止整數溢出。這是動態規劃算法中常見的邊界檢查和安全性措施。
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];}
};
?零錢和
322. 零錢兌換 - 力扣（LeetCode）
class Solution {
public:int coinChange(vector<int>& coins, int amount) {vector<int> dp(amount + 1, INT_MAX);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 - coins[i]] + 1, dp[j]);}}}if (dp[amount] == INT_MAX) return -1;return dp[amount];}
};單詞拆分
139. 單詞拆分 - 力扣（LeetCode）
要考慮for循環的先后順序
lass 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 = 0; j < wordDict.size(); j++) { // 物品for (int i = wordDict[j].size(); i <= s.size(); i++) { // 背包string word = s.substr(i - wordDict[j].size(), wordDict[j].size());if ( word == wordDict[j] && dp[i - wordDict[j].size()]) {dp[i] = true;}}}return dp[s.size()];}
};打家劫舍
打家劫舍
相鄰房間不能偷，考慮兩種情況，偷或者不偷
198. 打家劫舍 - 力扣（LeetCode）
class Solution {
public:int rob(vector<int>& nums) {if (nums.size() == 0) return 0;if (nums.size() == 1) return nums[0];vector<int> dp(nums.size());dp[0] = nums[0];dp[1] = max(nums[0], nums[1]);for (int i = 2; i < nums.size(); i++) {dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);}return dp[nums.size() - 1];}
};打家劫舍II
和上一題不同點：首尾相連連成環
情況如下
- 不考慮首尾元素，首尾元素連成環無影響
- 考慮首元素，默認沒有尾元素，但頭元素可選可不選
- 考慮尾元素，默認沒有首元素，但尾元素可選可不選
情況2,3包含了情況1，所以分成兩種情況，分別取兩種情況的最大值
class Solution {
public:int rob(vector<int>& nums) {if (nums.size() == 0) return 0;if (nums.size() == 1) return nums[0];int result1 = robRange(nums, 0, nums.size() - 2); int result2 = robRange(nums, 1, nums.size() - 1); return max(result1, result2);}int robRange(vector<int>& nums, int start, int end) {if (end == start) return nums[start];vector<int> dp(nums.size());dp[start] = nums[start];dp[start + 1] = max(nums[start], nums[start + 1]);for (int i = start + 2; i <= end; i++) {dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);}return dp[end];}
};?打家劫舍III
337. 打家劫舍 III - 力扣（LeetCode）
遍歷方式：后序遍歷
與前兩題的不同點是這個是在二叉樹的結構當中
class Solution {
public:int rob(TreeNode* root) {vector<int> result = robTree(root);return max(result[0], result[1]);//根節點投或者不投}// 長度為2的數組，0：不偷，1：偷vector<int> robTree(TreeNode* cur) {if (cur == NULL) return vector<int>{0, 0};vector<int> left = robTree(cur->left);//左子樹vector<int> right = robTree(cur->right);//右子樹// 偷cur，那么就不能偷左右節點。int val1 = cur->val + left[0] + right[0];// 不偷cur，那么可以偷也可以不偷左右節點，則取較大的情況int val2 = max(left[0], left[1]) + max(right[0], right[1]);return {val2, val1};}
};
