题目1： 1049. 最后一块石头的重量 II
算法思路： 这道题目跟leetcode 416类似，只是需要计算的是最大可能元素和。
代码如下：

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int sum = 0;
        for(int i = 0; i < stones.size(); i++) sum += stones[i];
        int target = sum / 2;

        int m = stones.size(), n = target + 1;
        vector<vector<int>> dp(m, vector<int>(n));
        for(int j = 0; j < n; j++) {
            if(stones[0] <= j) dp[0][j] = stones[0];
        }
        for(int i = 1; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(j >= stones[i]) dp[i][j] = max(dp[i-1][j], dp[i-1][j-stones[i]] + stones[i]);
                else dp[i][j] = dp[i-1][j];
            }
        }
        return sum - 2 * dp[m - 1][target];
    }
};

题目2: 494. 目标和
算法思路： 只需要找出左半部分等于(target+sum(数组))/2的总个数。
代码：

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum = 0;
        for(int i = 0; i < nums.size(); i++) sum += nums[i];
        if(abs(target) > sum) return 0;
        if((target + sum) & 1) return 0;

        int m = nums.size(), n = (target + sum) / 2;
        vector<vector<int>> dp(m, vector<int>(n + 1));
        if(nums[0] <= n) dp[0][nums[0]] = 1;

        int count = 0;
        for(int i = 0; i < m; i++) {
            if(nums[i] == 0) ++count;
            dp[i][0] = pow(2, count);
        }

        for(int i = 1; i < m; i++) {
            for(int j = 0; j <= n; j++) {
                if(nums[i] > j) dp[i][j] = dp[i - 1][j];
                else dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]];
            }
        }

        return dp[m - 1][n];
    }
};

题目3： 474. 一和零
时间不足，抄一下代码
代码：

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<vector<int>> dp(m + 1, vector<int> (n + 1, 0)); // 默认初始化0
        for (string str : strs) { // 遍历物品
            int oneNum = 0, zeroNum = 0;
            for (char c : str) {
                if (c == '0') zeroNum++;
                else oneNum++;
            }
            for (int i = m; i >= zeroNum; i--) { // 遍历背包容量且从后向前遍历！
                for (int j = n; j >= oneNum; j--) {
                    dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
                }
            }
        }
        return dp[m][n];
    }
};