关键是如何将问题化解为背包问题，并确定bagSize和dp数组的定义

补充，倒序的容量遍历，每次遍历到dp[j]都是选择上一个物品取否的值，对于本次遍历的物品来说，就相当于没选择本次物品，而dp[j-space[本次物品]]+value[本次物品]就是选择了一次本次物品的值；所以拿他们两个比较

LeetCode 1049

题目链接：最后一块石头的重量II
分成和尽量接近的两组

class Solution {
    public int lastStoneWeightII(int[] stones) {
        int sum = Arrays.stream(stones).sum();
        int bagSize = sum>>1;
        int[] dp = new int[bagSize+1];
        for(int i=0; i<stones.length; i++){
            for(int j=bagSize; j>=stones[i]; j--){
                dp[j] = Math.max(dp[j], dp[j-stones[i]]+stones[i]);
            }
        }
        return sum - 2*dp[bagSize]; 
    }
}

LeetCode 494

题目链接：目标和
一开始做的时候，思路局限在回溯的+或者-中，其实这道题可以转换为left组合 - right组合 = target，又right = sum - left所以left = (sum+target)/2，这样题目就变成了在这组数中，找到和为left的组合数量

换成01背包，数字就是物品，背包大小就是left，dp数组定义为，dp[j]和为j的组合数量，由此得到递推公式

注意这里的初始化要为dp[0]=1;

再总结，这两道应用题都是先分组，化解为01背包，再确定bagSize

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        // 把这个问题转换为
        // left组合 - right组合 = target
        // right = sum - left; left = (sum+target)/2
        // 其实和上一题是一样的

        int sum = Arrays.stream(nums).sum();
        // 考虑不存在的情况
        if (Math.abs(target) > sum) return 0;
        if((sum+target)%2==1) return 0;
        int bagSize = (sum+target)/2;
        // dp数组定义为，和为j的组合数量
        int[] dp = new int [bagSize+1];
        // 初始化dp数组，重点
        dp[0] = 1;
        for(int i=0; i<nums.length; i++){
            for(int j=bagSize; j>=nums[i]; j--){
                dp[j] += dp[j-nums[i]];
            }
        }
        return dp[bagSize];
    }
}

LeetCode 474

题目链接：一零和
就是一个二维0-1背包问题

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        // dp[m][n]为最多有m个0和n个1的最大子集
        int[][] dp = new int[m+1][n+1];

        for(int i=0; i<strs.length; i++){
            int n_m = 0;
            int n_n = 0;
            for(int j=0; j<strs[i].length();j++){
                if(strs[i].charAt(j)=='0'){
                    n_m++;
                }else{
                    n_n++;
                }
            }
            for(int j=m; j>=n_m; j--){
                for(int k=n; k>=n_n; k--){
                    dp[j][k] = Math.max(dp[j][k], dp[j-n_m][k-n_n]+1);
                }
            }
        }
        return dp[m][n];
    }
}