经典动态规划：背包问题-（LC474）

题目：给定 m 个数字 0 和 n 个数字 1，以及一些由 0-1 构成的字符串，求利用这些数字最多可以构成多少个给定的字符串，字符串只可以构成一次。

思路：

把总共的 0 和 1 的个数视为背包的容量，每一个字符串视为装进背包的物品。这道题就可以使用 0-1 背包问题的思路完成，这里的目标值是能放进背包的字符串的数量

动态规划的思路是：物品一个一个尝试，容量一点一点尝试，每个物品分类讨论的标准是：选与不选。

定义状态：尝试题目问啥，就把啥定义成状态。dp[i][j][k] 表示输入字符串在子区间 [0, i] 能够使用 j 个 0 和 k 个 1 的字符串的最大数量。

初始化：为了避免分类讨论，通常多设置一行。这里可以认为，第 0 个字符串是空串。第 0 行默认初始化为 0。
输出：输出是最后一个状态，即：dp[len][m][n]。

结合代码与注释理解：

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
   int length=strs.length;
   int [][][]dp=new int [length+1][m+1][n+1];//数组+1是为了不溢出吧
   for(int i=1;i<=length;i++){//对比下面的字符串有=
             int[]zerosOnes=getZerosOnes(strs[i-1]);
             int zeros=zerosOnes[0],ones=zerosOnes[1];
            for(int j=0;j<=m;j++){
                for(int k=0;k<=n;k++){
                dp[i][j][k]=dp[i-1][j][k];//j和k都小于上面的zeros，ones时，不选第i个字符串的情况
            if(j>=zeros&&k>=ones){//都大于时，选与不选第i个字符串的2个情况，选最大的情况
                 dp[i][j][k]=Math.max(dp[i][j][k],dp[i-1][j-zeros][k-ones]+1);
                   }
                }
             }
         }
         return dp[length][m][n];
   }
   //计算1和0的数量？
  public int[]getZerosOnes(String str){
      int []zerosOnes=new int[2];
      int length=str.length();//字符串加括号
      for(int i=0;i<length;i++){//字符串没有=
        zerosOnes[str.charAt(i)-'0']++;//这是计算01的数量？

      }
      return zerosOnes;
 
    }
}