C++의 1과 0

<시간/>

각각 m 0s와 n 1s의 도미네이터가 있다고 가정합니다. 반면에 이진 문자열이 있는 배열이 있습니다. 이제 우리의 임무는 주어진 m 0과 n 1에서 생성할 수 있는 최대 문자열 수를 찾는 것입니다. 0과 1은 각각 최대 한 번만 사용할 수 있습니다. 따라서 입력이 Array =["10", "0001", "111001", "1", "0",] 및 m =5 및 n =3과 같으면 출력은 4가 됩니다. 5개의 0과 3개의 1을 사용하여 "10,"0001","1","0"인 총 4개의 문자열을 만들 수 있습니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

(m + 1) x (n + 1) 크기의 행렬 만들기
ret :=0
범위 0에서 strs 배열 크기까지의 경우
- 1 :=0, 0 :=0
- 범위 0에서 strs[i]
  - star[i, j]가 1이면 1 증가, 0이면 0 증가
- m 범위에서 0까지의 j에 대해
  - n 범위에서 1까지의 j에 대해
    - dp[j,k] :=dp[j,k] 및 1 + dp[j – 0, k – 1]의 최대값
    - ret :=ret 및 dp[j,k]의 최대값
반환

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int findMaxForm(vector<string>& strs, int m, int n) {
      vector < vector <int> > dp(m + 1, vector <int>(n + 1));
      int ret = 0;
      for(int i = 0; i < strs.size(); i++){
         int one = 0;
         int zero = 0;
         for(int j = 0; j < strs[i].size(); j++){
            one += strs[i][j] == '1';
            zero += strs[i][j] == '0';
         }
         for(int j = m; j>= zero; j--){
            for(int k = n; k >= one; k--){
               dp[j][k] = max(dp[j][k], 1 + dp[j - zero][k - one]);
                  ret = max(ret, dp[j][k]);
            }
         }
      }
      return ret;
   }
};
main(){
   vector<string> v = {"10","0001","111001","1","0"};
   Solution ob;
   cout << (ob.findMaxForm(v, 5, 3));
}

입력

["10","0001","111001","1","0"]
5
3