本文最后更新于 699 天前，其中的信息可能已经有所发展或是发生改变。
思路
多维的动态规划，属于背包类问题，只是穷举多了个背包。
strs里的每个元素就是物品，m为装1的背包数量，n为装0的背包数量，开始DP套路：
定义状态：dp[i][m][n]表示0-i个物品，m个装1的背包，n个装0的背包可以装下多少个物品
状态转移方程：dp[i][m][n]=max(dp[i-1][m][n],dp[i-1][m-i1][n-i0]+1)
初始值：dp[0][m][n]=0优化
由于dp[i][m][n]的取值都来源于dp[i-1][m][n]，那么可以直接用二维数组，只是每次放物品时，都在同一个二维数组上操作，也就是基于上一个物品的二维数组计算。这就是滚动数组的由来，需要满足的条件是：上一层可以重复利用，直接拷贝到当前层。
正序遍历背包数量时，三维数组用到了dp[i-1][m-i1][n-i0]，现在是dp[m-i1][n-i0]，因为是正序，所以这个值是在dp[m][n]计算前就计算过了，也就是被覆盖了，不再等于dp[i-1][m-i1][n-i0]。而后序遍历可以正常计算，计算dp[m][n]时，dp[m-i1][n-i0]还没使用过，就是之前的值。
题目
代码
func findMaxFormOld(strs []string, m int, n int) int {
dp := iniDpArr(strs, m, n)
for i, str := range strs {
zeroCount, oneCount := countOfZeroAndOne(str)
// 当前物品固定，穷举背包数量
for j := 0; j <= m; j++ {
for k := 0; k <= n; k++ {
// 装不下该物品 = 不装
if j < zeroCount || k < oneCount {
dp[i+1][j][k] = dp[i][j][k]
} else {
dp[i+1][j][k] = max(dp[i][j][k], dp[i][j-zeroCount][k-oneCount]+1)
}
}
}
}
return dp[len(strs)][m][n]
}
// 优化后
func findMaxForm(strs []string, m int, n int) int {
dp := make([][]int, m+1)
for i := range dp {
dp[i] = make([]int, n+1)
}
for _, s := range strs {
zeros := strings.Count(s, "0")
ones := len(s) - zeros
for j := m; j >= zeros; j-- {
for k := n; k >= ones; k-- {
dp[j][k] = max(dp[j][k], dp[j-zeros][k-ones]+1)
}
}
}
return dp[m][n]
}
func countOfZeroAndOne(str string) (int, int) {
var zeroCount, oneCount int
for _, char := range str {
if '0' == char {
zeroCount++
} else if '1' == char {
oneCount++
}
}
return zeroCount, oneCount
}
func iniDpArr(strs []string, m int, n int) [][][]int {
var dp = make([][][]int, len(strs)+1)
for i := range dp {
dp[i] = make([][]int, m+1)
for j := range dp[i] {
dp[i][j] = make([]int, n+1)
}
}
return dp
}
func max(i int, i2 int) int {
if i > i2 {
return i
}
return i2
}
