2.11-背包问题

分析：经典背包问题。

class Solution {
public:bool canPartition(vector<int>& nums) {int n = nums.size();int sum = 0;for (auto e : nums) sum += e;if (sum % 2 == 1) return false;int half = sum / 2;vector<vector<bool>> dp(n + 1, vector<bool>(half + 1));for (int i = 0; i < n + 1; i++) dp[i][0] = true;for (int i = 1; i < n + 1; i++)for (int j = 1; j < half + 1; j++) {dp[i][j] = dp[i - 1][j];if (j >= nums[i - 1]) {dp[i][j] = dp[i][j] || dp[i - 1][j - nums[i - 1]];}}return dp[n][half];}
};

分析：还可用滚动数组优化。

class Solution {
public:bool canPartition(vector<int>& nums) {int n = nums.size();int sum = 0;for (auto e : nums) sum += e;if (sum % 2 == 1) return false;int half = sum / 2;vector<bool> dp(half + 1);dp[0] = true;for (int i = 1; i < n + 1; i++)for (int j = half; j > 0 && j >= nums[i - 1]; j--)dp[j] = dp[j] || dp[j - nums[i - 1]];return dp[half];}
};

class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {int sum = 0;for (auto e : nums) sum += e;if ((sum - target) % 2 == 1 || sum - target < 0) return 0;int aim = (sum - target) / 2;vector<int> dp(aim + 1);dp[0] = 1;for (int i = 1; i < nums.size() + 1; i++)for (int j = aim; j >= nums[i - 1]; j--)dp[j] += dp[j - nums[i - 1]];return dp[aim];}
};

分析：先把问题转化为背包问题，即：先用bool的dp数组，找到将石头分为两份的所有可能中最接近五五开的，然后再遍历dp即可。

class Solution {
public:int lastStoneWeightII(vector<int>& stones) {int sum = 0;for (auto e : stones) sum += e;int m = sum / 2;vector<bool> dp(m + 1);dp[0] = true;for (auto e : stones) {for (int j = m; j >= e; j--) {dp[j] = dp[j] || dp[j - e];}}for (int i = m;; i--) if (dp[i]) return sum - 2 * i;}
};

分析：从本题开始属于完全背包问题。

class Solution {
public:int coinChange(vector<int>& coins, int amount) {vector<int> dp(amount + 1, -1);dp[0] = 0;for (int e : coins) {for (int j = e; j < amount + 1; j++) {if (dp[j - e] != -1) {if (dp[j] == -1) {dp[j] = dp[j - e] + 1;} else {dp[j] = min(dp[j], dp[j - e] + 1);}}}}return dp[amount];}
};	

分析：这个题的数据中间会爆int，只有用unsigned long long才能过。

class Solution {
public:int change(int amount, vector<int>& coins) {vector<unsigned long long> dp(amount + 1, 0);dp[0] = 1;for (auto e : coins)for (unsigned long long j = 1; j < amount + 1; ++j) {if (j >= e) {dp[j] += dp[j - e];}}return (int)dp[amount];}
};

分析：和零钱兑换如出一辙。

class Solution {
public:int numSquares(int n) {vector<int> dp(n + 1);for (int e = 1; e * e <= n; e++)for (int j = e * e; j < n + 1; j++) {if (dp[j] == 0) {dp[j] = dp[j - e * e] + 1;} else {dp[j] = min(dp[j], dp[j - e * e] + 1);}}return dp[n];}
};

分析：本题与下一题属于二位费用的背包问题，同样也可以优化为二维滚动数组，这里就不优化了。

class Solution {
public:int findMaxForm(vector<string>& strs, int m, int n) {int len = strs.size();vector<vector<vector<int>>> dp(len + 1, vector<vector<int>>(m + 1, vector<int>(n + 1, 0)));for (int i = 1; i <= len; ++i) {int a = 0, b = 0;for (char ch : strs[i - 1]) {if (ch == '0') {a++;} else {b++;}}for (int j = 0; j <= m; ++j) {for (int k = 0; k <= n; ++k) {dp[i][j][k] = dp[i - 1][j][k];if (j >= a && k >= b) {dp[i][j][k] =max(dp[i][j][k], dp[i - 1][j - a][k - b] + 1);}}}}return dp[len][m][n];}
};

class Solution {
public:int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) {const int MOD = 1e9 + 7;int len = group.size();vector<vector<vector<int>>> dp(len + 1, vector<vector<int>>(n + 1, vector<int>(minProfit + 1, 0)));for (int j = 0; j <= n; j++) dp[0][j][0] = 1;for (int i = 1; i <= len; ++i) {for (int j = 0; j <= n; ++j) {for (int k = 0; k <= minProfit; ++k) {dp[i][j][k] = dp[i - 1][j][k];if (j >= group[i - 1]) {dp[i][j][k] += dp[i - 1][j - group[i - 1]][max(0, k - profit[i - 1])];dp[i][j][k] %= MOD;}}}}return dp[len][n][minProfit] % MOD;}
};

分析：由于本题的物品存放需要考虑顺序，所以要先遍历背包再遍历物品。并且此题用int存储会爆。

class Solution {
public:int combinationSum4(vector<int>& nums, int target) {vector<unsigned long long> dp(target + 1, 0);dp[0] = 1;for (unsigned long long j = 1; j < target + 1; j++) {for (auto e : nums) {if (j >= e)dp[j] += dp[j - e];}}return (int)dp[target];}
};