一、背包能否裝滿？

416. 分割等和子集

class Solution {
public:// 01背包：逆序遍歷// 組合問題：先背包后容量bool canPartition(vector<int>& nums) {int m = nums.size();int sum = accumulate(nums.begin(), nums.end(), 0);if(sum & 1) return false;int n = sum / 2;vector<int> dp(n + 1, 0);        // dp[j]：容量為j的背包，最多裝入重量為dp[j]的物品for(int i = 0; i < m; i++){for(int j = n; j >= nums[i]; j--){dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);}}return dp[n] == n;}
};

dp背包問題——416. 分割等和子集

1049. 最后一塊石頭的重量 II

class Solution {
public:// 01背包：逆序遍歷// 組合問題：先物品、后容量int lastStoneWeightII(vector<int>& stones) {int m = stones.size();int sum = accumulate(stones.begin(), stones.end(), 0);int n = sum / 2;vector<int> dp(n + 1, 0);  // dp[j]：容量為j的背包，最多裝dp[j]的石頭for(int i = 0; i < m; i++){for(int j = n; j >= stones[i]; j--){dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);}}return sum - 2 * dp[n];}
};

dp背包問題——1049. 最后一塊石頭的重量 II

二、裝滿背包有幾種方法？

494. 目標和

class Solution {
public:// 01背包：逆序遍歷// 組合問題：先物品，后容量int findTargetSumWays(vector<int>& nums, int target) {int sum = accumulate(nums.begin(), nums.end(), 0);if((sum + target) & 1) return 0;int m = nums.size();int n = (sum + target) / 2;if(n < 0) return 0;vector<int> dp(n + 1, 0);  // dp[j]：裝滿容量為j的背包，有dp[j]種方法dp[0] = 1;                 // 裝滿容量為0的背包，只有1種方法for(int i = 0; i < m; i++){for(int j = n; j >= nums[i]; j--){// 多了一個物品可選擇后，裝滿背包的方法數(shù)就是 ：（沒有當前物品可選時的方法數(shù) + 選了當前物品的方法數(shù)）dp[j] = dp[j] + dp[j - nums[i]];}}return dp[n];}
};

dp背包解決組合問題——494. 目標和

518.零錢兌換II

class Solution {
public:// 完全背包：順序遍歷// 組合問題：先物品、后容量int change(int amount, vector<int>& coins) {int m = coins.size();int n = amount;vector<int> dp(n + 1, 0);  // dp[j]：裝滿容量為j的背包，有dp[j]種方式dp[0] = 1;for(int i = 0; i < m; i++){for(int j = coins[i]; j <= n; j++){// 多了一個物品可選后，裝滿背包的方法數(shù)就是 ：（沒有當前物品可選時的方法數(shù) + 選了當前物品的方法數(shù)）dp[j] = dp[j] + dp[j - coins[i]];}}return dp[n];}
};

dp完全背包問題解組合問題——零錢兌換

377. 組合總和 Ⅳ

class Solution {
public:// 完全背包：順序遍歷// 排列問題：先容量，后物品int combinationSum4(vector<int>& nums, int target) {int m = nums.size();int n = target;vector<int> dp(n + 1, 0); // dp[j]：裝滿容量為j的背包，物品的組合數(shù)為dp[j]dp[0] = 1;for(int j = 1; j <= n; j++){for(int i = 0; i < m; i++){if(j >= nums[i] && dp[j] < INT_MAX - dp[j - nums[i]]) dp[j] += dp[j - nums[i]];}}return dp[n];}
};

70. 爬樓梯

class Solution {
public:// 完全背包：順序遍歷// 排列問題：先容量，后物品int climbStairs(int n) {int m = 2;int nums[2] = {1,2};vector<int> dp(n + 1, 0);  // dp[j]：裝滿容量為j的背包，有dp[j]種方法dp[0] = 1;for(int j = 1; j <= n; j++){for(int i = 0; i < m; i++){if(j >= nums[i]) dp[j] = dp[j] + dp[j - nums[i]];}}return dp[n];}
};

排列問題：先容量，后物品

如果物品為{1，2}，假如此時容量為2（容量為1的背包只能裝物品1），用當前容量遍歷多個物品，可以選擇在裝了物品1的基礎(chǔ)上接著裝，也可以選擇不在其基礎(chǔ)上裝，直接裝入物品2。當容量為3時，也可以選擇在裝有物品2的基礎(chǔ)上再裝入物品1，這樣就出現(xiàn)了{2，1}

組合問題：先物品，后容量

如果物品為{1，2，3}，假如此時容量為5

只有物品1，用各個容量遍歷，此時無論是什么容量的背包，都只能放入物品1
此時我們手拿著物品2，對于每一個容量，要么直接使用現(xiàn)在就裝滿的背包，要么找一個剩余容量為2的背包放入當前物品2
接著我們手拿著物品3，對于每一個容量，要么直接使用現(xiàn)在就裝滿的背包，要么找一個剩余容量為3的背包放入當前物品3

class Solution {
public:int climbStairs(int n) {vector<int> dp(n + 1, 0);dp[0] = 1;dp[1] = 1;for(int i = 2; i <= n; i++){dp[i] = dp[i - 2] + dp[i - 1];  // 要么爬1個臺階，要么2個臺階}return dp[n];}
};

三、背包裝滿的最大價值

474.一和零

class Solution {
public:// 01背包：逆序遍歷// 組合問題：先物品、后容量int findMaxForm(vector<string>& strs, int m, int n) {vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));  // dp[i][j]：裝滿容量為ij背包的最大價值for(string& s : strs){int w0 = 0;int w1 = 0;for(char c : s){if(c == '0') w0++;else w1++;}// 每次循環(huán)計算出的dp[m][n]表示只有前幾個物品可選時，所獲得的最大價值for(int i = m; i >= w0; i--){for(int j = n; j >= w1; j--){dp[i][j] = max(dp[i][j], dp[i - w0][j - w1] + 1);  // 1表示價值}}}return dp[m][n];}
};

四、裝滿背包最小物品數(shù)

322. 零錢兌換

class Solution {
public:// 問裝滿背包需要最少的物品數(shù)int coinChange(vector<int>& coins, int amount) {// 完全背包：順序遍歷// 組合問題：先物品、后容量，裝滿就行，不在意裝入的順序int m = coins.size();int n = amount;// 湊成面值n，最多需要n個硬幣，初始化為n + 1即可vector<int> dp(n + 1, n + 1); // dp[j]：裝滿容量為j的背包至少需要dp[j]個物品dp[0] = 0;for(int i = 0; i < m; i++){for(int j = coins[i]; j <= n; j++){// 裝滿容量為j的背包，要么直接用前面的物品裝滿，要么找一個剩余容量為coins[i]的背包放入coins[i]dp[j] = min(dp[j], dp[j - coins[i]] + 1);  }}return dp[n] == n + 1 ? -1 : dp[n];}
};

279.完全平方數(shù)

class Solution {
public:// 物品為：[1,4,9,...]// 容量為n，問裝滿背包至少需要幾個物品int numSquares(int n) {// 完全背包：順序遍歷// 組合問題：先物品、后容量vector<int> dp(n + 1, n);dp[0] = 0;for(int i = 1; i <= n / i; i++){for(int j = i * i; j <= n; j++){dp[j] = min(dp[j], dp[j - i * i] + 1);}}return dp[n];}
};