leetcode 474. Ones and Zeroes

원제 주소

https://leetcode.com/problems/ones-and-zeroes/description/

제목의 뜻

01열을 포함하는 벡터를 정하고, 사용할 수 있는 0과 1의 수를 정하며, 사용할 수 있는 범위 내에서 벡터에서 01열을 선택하고, 최대 벡터에서 01열을 얼마나 고를 수 있는지 구합니다.

사고의 방향

가방 문제의 변형이죠.점차적인 방정식은 dp[i][j][k]=max(dp[i-1]j[k], dp[i-1]j-count1(str[i])][k-count0(str[i])]) dp[i][j][k]는 앞의 i열을 표시하고 j개의 1, k개의 0을 정한 상황에서 꺼낼 수 있는 열의 수를 정한다.(코드에서 i, j, k는 모두 1부터 계산한다)

코드

1

다음 코드를 제출하여 runtime error를 받았습니다. 실패한 예를 보면 01열의 수가 너무 많아서 dp수조가 너무 터졌을 것입니다.

class Solution {
public:
    int count0(string s) {
        int count = 0;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '0') count++;
        }
        return count;
    }

    int count1(string s) {
        int count = 0;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '1') count++;
        }
        return count;
    }

    int findMaxForm(vector& strs, int m, int n) {

        int s = strs.size();
        int dp[s + 1][m + 1][n + 1];

        for (int j = 0; j <= m; j++) {
            for (int k = 0; k <= n; k++) {
                dp[0][j][k] = 0;
            }
        }


        for (int i = 1; i <= s; i++) {
            for (int j = 0; j <= m; j++) {
                for (int k = 0; k <= n; k++) {
            
                    int temp = 0;
                    if (j  >= count0(strs[i-1])  && k  >= count1(strs[i-1]) ) {
                        temp = dp[i - 1][j - count0(strs[i-1])][k  - count1(strs[i-1])] + 1;
                    }
                    dp[i][j][k] = max(dp[i - 1][j][k], temp);
                }
            }
        }
        return dp[s ][m ][n ];
    }
};

그래서 아래 공간의 복잡도를 최적화하고 문자열의 수를 나타내는 1차원을 제거한다

2

class Solution {
public:
    int count0(string s) {
        int count = 0;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '0') count++;
        }
        return count;
    }

    int count1(string s) {
        int count = 0;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '1') count++;
        }
        return count;
    }

    int findMaxForm(vector& strs, int m, int n) {
        int s = strs.size();
        int dp[m + 1][n + 1];

        for (int j = 0; j <= m; j++) {
            for (int k = 0; k <= n; k++) {
                dp[j][k] = 0;
            }
        }
        for (int i = 1; i <= s; i++) {
            for (int j = m; j >= 0; j--) {
                for (int k = n; k >= 0; k--) {
                    int temp = 0;
                    if (j  >= count0(strs[i - 1])  && k  >= count1(strs[i - 1]) ) {
                        temp = dp[j - count0(strs[i - 1])][k  - count1(strs[i - 1])] + 1;
                    }
                    dp[j][k] = max(dp[j][k], temp);
                }
            }
        }
        return dp[m ][n ];
    }
};