最近正在死磕动态规划，前阵子把Leetcode上的动态规划标签的简单题刷完了(其实一共也才5题)，最近在看动态规划中经典的0-1背包问题，顺便在Leetcode上就找了这个练习题。题目如下：

In the computer world, use restricted resource you have to generate maximum benefit is what we always want to pursue.
For now, suppose you are a dominator of m 0s and n 1s respectively. On the other hand, there is an array with strings consisting of only 0s and 1s.
Now your task is to find the maximum number of strings that you can form with given m 0s and n 1s. Each 0 and 1 can be used at most once.
Note:

  1. The given numbers of 0s and 1s will both not exceed 100
  2. The size of given string array won’t exceed 600.

Example 1:

1
2
3
Input: Array = {"10", "0001", "111001", "1", "0"}, m = 5, n = 3
Output: 4
Explanation: This are totally 4 strings can be formed by the using of 5 0s and 3 1s, which are “10,”0001”,”1”,”0”

Example 2:

1
2
3
Input: Array = {"10", "0", "1"}, m = 1, n = 1
Output: 2
Explanation: You could form "10", but then you'd have nothing left. Better form "0" and "1".

题目大意

给定一个字符串数组以及整数m和n，m和n分别代表着0和1的个数，求出这些0和1能组成字符串数组中字符串的最大个数。如：

给定数组{"10", "0", "1"},以及m = 1, n = 1。那么输出为2，1个0和1个1可以组成字符串数组的中的二三两个字符串。

思路

第一种解法

这是一个多维的0-1背包问题，只是把背包容量的大小换成了0和1的个数，而宝石换成了字符串，宝石的重量为字符串中0和1的个数，宝石价值都为1。

状态和递推式和0-1背包问题类似。因为“背包”容量是2维的，所以存储状态的数组是3维的，状态dp[i][j][k]表示前i个字符串中能用j个0和k个1组成的最大字符串数。这样的话状态就已经确定下来，剩下的就是寻找转移方程了。

字符串之间的转移是如何进行的呢？其实当我们考虑dp[i][j][k]时，我们讨论的是要不要组成第i个字符串，假设第i个字符串的0和1的个数分别为zeros和ones。如果不组成这个字符串，那么dp[i][j][k]的值就和dp[i - 1][j][k]的值是一样的；如果组成这个字符串，那么dp[i][j][k]就应该是dp[i - 1][j - zeros][k - ones] + 1，也即前i - 1的字符串中除去第i个字符串使用的0和1所剩下的0和1所能组成的最大字符串数量再加上1（组成了第i个字符串，所以+1）。这样就得到了递推式：

dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j - zeros][k - ones])

这个算法的时间复杂度为O(lmn)，其中l是字符串数组的长度，空间复杂度也是O(lmn)，Java版的代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
public class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int l = strs.length;
        int [][][] d = new int[l + 1][m + 1][n + 1];     
        for (int i = 0; i <= l; i ++){
            int [] nums = new int[]{0,0};
            if (i > 0){
               nums = getNum(strs[i - 1]);
            }         
            for (int j = 0; j <= m; j ++){
                for (int k = 0; k <= n; k ++){
                    if (i == 0) {
                        d[i][j][k] = 0;
                    } else if (j >= nums[0] && k >= nums[1]){
                        d[i][j][k] = Math.max(d[i - 1][j][k], d[i - 1][j - nums[0]][k - nums[1]] + 1);
                    } else {
                        d[i][j][k] = d[i - 1][j][k];
                    }     
                    
                }
            }           
        }
        return d[l][m][n];
    }
     // this method is used to get the count of 0 and 1
    private int [] getNum(String str){
        int [] nums = new int [2];
        for (int i = 0; i < str.length(); i++){
            if (str.charAt(i) == '0') {
                nums[0] ++;
            } else {
                nums[1] ++;
            }
        }
        return nums;
    }
}

提交Leetcode，结果如图

运行结果
运行结果

0-1背包问题中的空间优化方法

0-1背包问题有优化空间复杂度的方法。类似的，这一题也可以将三维的数组优化成二维，字符串数量那一维删去，就可以得到空间复杂度为O(mn)的算法。

以下图的0-1背包问题作为讲解。

状态数组
状态数组

我们可以看到，在每一次计算d[i][j]时，我们并没有用到所有的状态，只是前一行的两个状态。这样的话状态存储的就能从L x m优化成2 x m，然后轮流使用这两行进行状态即可。

但是轮流使用还是很麻烦，那么有没有进一步的优化空间呢。从上面的递推式我们可以发现，当前的状态仅仅使用上一行的两个位置的状态，那么我们完全可以使用1 x m的数组进行存储。那么状态转移方程就变成了

d[j] = max(d[j], d[j - w] + v)

d[i - 1][j - w] d[i - 1][j]
d[i][j]

左边的d[j]是第二行的d[i][j]，而右边是上一行的d[i - 1][j]，d[j - w]也是上一行的d[i - 1][j - w]。但是这样有个问题，如果d[i][j + 1]在更新的时候刚好要用到d[i - 1][j]，而这个时候d[i - 1][j]已经被更新成为了d[i][j]，那么结果就会出现错误。如果解决这个问题呢？其实只需要将j的迭代顺序从0 -> N变成倒序即N -> 0即可。这样的话就算d[i][j + 1]在更新的时候要用上d[i - 1][j]，d[j]也就是旧的还未更新之前的d[i - 1][j]。这样就将0-1背包的空间复杂度从O(lm)降到了O(m)。

Ones and Zeros 问题中的空间优化方法

类似于上面的0-1背包问题，在计算dp[i][j][k]时，我们只用到了dp[i - ][j][k]和dp[i - 1][j - zeros][k - ones]两个状态，因此将第二维和第三维的循环变量倒序，然后修改一下状态转移方程为

d[j][k] = max(d[j][k], d[j - zeros][k - ones] + 1)

这样把上一版的Java的代码修改如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int l = strs.length;
        int [][] dp = new int[m + 1][n + 1];     
        for (int i = 0; i < l; i ++){
            int [] nums = getNum(strs[i]);
            for (int j = m; j >= nums[0]; j --){
                for (int k = n; k >= nums[1]; k --){
                    dp[j][k] = Math.max(dp[j][k], dp[j - nums[0]][k - nums[1]] + 1);                    
                }
            }
        }
        return dp[m][n];
    }
    
    // this method is used to get the count of 0 and 1
    private int [] getNum(String str){
        int [] nums = new int [2];
        for (int i = 0; i < str.length(); i++){
            if (str.charAt(i) == '0') {
                nums[0] ++;
            } else {
                nums[1] ++;
            }
        }
        return nums;
    }
}

第二版不仅复杂度降了很多，代码也变简单了。提交Leetcode结果如下：

提交结果
提交结果

总结

死磕动态规划也有一段时间了，总算会了一些，不像之前没学过那样磕磕碰碰看的头大了。其实动态规划都有其一定的规律，主要是定义状态以及状态转移方程，将大问题转化成子问题，最终一步步优化得到最后的结果。