[Leetcode] 474. Ones and Zeroes 解題報告

題目：

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 

 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:

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:

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".      

思路：

又是動态規劃的一個變種。我們定義dp[i][j]表示從第0個字元串到截止目前字元串，用i個0和j個1可以構成的字元串的最大數目。那麼狀态轉移方程是：dp[i][j] = max(dp[i - zero_num][j - one_num])，其中zero_num和one_num分别是目前字元串中0和1的數目，i <= zero_num <= m, j <= one_num <= n。需要注意的是：我們必須從後往前更新，這是因為如果從前往後更新，那麼如果更新了dp[i][j]，就意味着目前dp[i][j]的數量已經包含了s，那麼在計算dp[i + ...][j + ...]的時候，用到的dp[i][j]是已經被更新過的（也就是包含了s的數量），是以就會導緻重複計算。

算法的時間複雜度是O(l * m * n)，其中l是字元串的數量。算法的空間複雜度是O(m*n)。

代碼：

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        for (auto &s : strs) {
            int numZeroes = 0, numOnes = 0;
            for (auto c : s) {
                if (c == '0')
                    numZeroes++;
                else if (c == '1')
                    numOnes++;
            }
            for (int i = m; i >= numZeroes; i--) {
                for (int j = n; j >= numOnes; j--) {
                    dp[i][j] = max(dp[i][j], dp[i - numZeroes][j - numOnes] + 1);
                }
            }
        }
        return dp[m][n];
    }
};