LeetCode#474

LeetCode#474一和零

链接
三维动规，可以循环判断每一个包含的字符串从而进行空间优化，注意在动规的时候需要从后往前找（即从m->cnt1,n->cnt2，从前往后会影响之前的状态改了好久，菜啊）动态规划可太快乐了。

class Solution {
public:
int dp[200][200];
    int findMaxForm(vector<string>& strs, int m, int n) {
        for(int i = 0 ; i < strs.size() ; i++)
        {
            int cnt1 = 0;
            int cnt2 = 0;
            for(int j  = 0 ; j < strs[i].size() ; j++)
            {
                if(strs[i][j] == '0')
                    cnt1++;
                else
                    cnt2++;
            }
            for(int j = m ; j >= cnt1 ;j --)
            {
                for(int k = n ; k >= cnt2 ; k --)
                {
                    dp[j][k] = max(dp[j][k],dp[j-cnt1][k-cnt2]+1);
                }
            }
        }
        return dp[m][n];
    }
};