Day 2 补充

分治算法是指将问题划分成一些 独立 的子问题，递归求解各子问题，然后合并子问题的解而得到原问题的解。与此不同，动态规划适用于子问题 不是独立 的情况，也就是各子问题包含公共的子子问题。在这种情况下，若用分治法则会做许多不必要的工作，即重复地求解公共的子子问题。
动态规划算法对每个子子问题只求解一次，将其结果保存在一张表种，从而避免每次遇到各子问题时重新计算答案。
动态规划通常应用于 最优化问题 。此类问题可能有很多种可行解。每个解有一个值，而我们希望找出一个具有最优（最大或最小）值的解。称这样的解为该问题的 一个 最优解（而不是确定的最优解），因为可能存在多个取最优值的解。
动态规划算法的设计可以分为以下四步：

1. 描述最优解的结构i
2. 递归定义最优解的值
3. 按自底向上的方式计算最优解的值
4. 由计算出的结果构造一个最优解

   474.一和零

   题目描述
   给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
   请你找出并返回 strs 的最大子集的大小，该子集中 最多 有 m 个 0 和 n 个 1 。
   如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。
   示例
   输入：strs = [“10”, “0001”, “111001”, “1”, “0”], m = 5, n = 3
   输出：4
   解释：最多有 5 个 0 和 3 个 1 的最大子集是 {“10”,”0001”,”1”,”0”} ，因此答案是 4 。
   其他满足题意但较小的子集包括 {“0001”,”1”} 和 {“10”,”1”,”0”} 。{“111001”} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。
   思路
   第一步，要明确两点，[状态]和[选择]。
   状态有三个， [背包对1的容量]、[背包对0的容量]和 [可选择的字符串]；选择就是把字符串[装进背包]或者[不装进背包]。
   第二步，要明确dp数组的定义：
   首先，[状态]有三个，所以需要一个三维的dp数组。dp[i][j][k]的定义如下：若只使用前i个物品，当背包容量为j个0，k个1时，能够容纳的最多字符串数。
   第三步，根据选择，思考状态转移的逻辑：
   注意，这是一个0-1背包问题，每个字符串只有一个选择机会，要么选择装，要么选择不装。
   如果你不能把这第 i 个物品装入背包 （等同于容量不足，装不下去），也就是说你不使用strs[i]这一个字符串，那么当前的字符串数dp[i][j][k]应该等于dp[i - 1][j][k], 继承 之前的结果。
   如果你可以把这第 i 个物品装入了背包 (此时背包容量是充足的，因此要选择装或者不装)，也就是说你能使用 strs[i] 这个字符串，那么 dp[i][j] 应该等于 Max(dp[i - 1][j][k], dp[i - 1][j - cnt[0]][k - cnt[1]] + 1)。 Max函数里的两个式子，分别是装和不装strs[i的字符串数量。(cnt 是根据strs[i]计算出来的。)

   class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int len = strs.length;
        int[][][] dp =new int[len+1][m+1][n+1];
        for(int i=1; i<=len; i++){
            String s = strs[i-1];
            int zeronum = countzero(s);
            int onenum = s.length()-zeronum;
            for(int j=0; j<m+1; j++){
                for(int k=0; k<n+1; k++){
                    dp[i][j][k]  = dp[i-1][j][k];
                    if(j>=zeronum && k>=onenum){
                        dp[i][j][k] = Math.max(dp[i-1][j][k],dp[i-1][j-zeronum][k-onenum]+1);
                    }
                }
            }
        }
        return dp[len][m][n];
    }
    public int countzero(String s){
        int count = 0;
        for(int i=0; i<s.length(); i++){
            if(s.charAt(i)=='0'){
                count++;
            }
        }
        return count;
    }
   }