动态规划— 一和零

class Solution {public int findMaxForm(String[] strs, int m, int n) {int[][] dp = new int[m+1][n+1];//dp[i][j]表示i个0和j个1时的最大子集int oneNum = 0, zeroNum = 0;for(String str : strs){oneNum = 0;zeroNum = 0;for(char c : str.toCharArray()){if(c == '0'){zeroNum++;}else{oneNum++;}}//dp[i][j] 可以由前一个strs里的字符串推导出来，strs里的字符串有zeroNum个0，oneNum个1for(int i = m; i>= zeroNum; i--){for(int j = n; j>= oneNum; j--){dp[i][j] = Math.max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);}}}return dp[m][n];}
}

确定dp数组以及下标的含义

       dp[i][j]：最多有i个0和j个1的strs的最大子集的大小为dp[i][j]。

确定递推公式

      递推公式：dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);

dp数组初始化

       dp[0] 初始为0 

确定遍历顺序

          遍历背包的for循环,  for循环倒序遍历

复杂度分析

• 时间复杂度: O(kmn)，k 为strs的长度
• 空间复杂度: O(mn)