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];
    }
};