dynamic programming question

Правка en1, от t3rminated, 2017-01-20 13:47:32

I am doing this question but i am only able to pass 36/60 test cases i can't find my mistake in code . here's my code -

int dp[104+1][104+1][605];
class Solution {
public:
int dd=0;
int freq[602][2];

    int findMaxForm(vector<string>& strs, int m, int n)
    {
        
        for(int i = 0; i <= m; i++)
        {
            for(int j = 0; j <= n; j++)
            { 
                for(int k = 0; k <= 604; k++)
                    dp[i][j][k] = -1;
            }
        }
        memset(freq, 0, sizeof freq);
        
        for(int i = 0; i < strs.size(); i++)
        {
            for(int j = 0; j < strs[i].length(); j++)
            {
               freq[i][strs[i][j] - '0']++; 
            }
        }
       return letsee(m, n, strs.size(),0);
    }
    
    int letsee(int m, int n, int len, int state)
    {
        // cout << m << " " << n << " "<<state<<"*"
        if(m == 0 && n == 0)return 0;
        if(m < 0 && n < 0)
            return -1;
        if(dp[m][n][state] != -1)
            return dp[m][n][state];
        for(int i = 0; i < len; i++)
        {
            if(m >= freq[i][0] && n >= freq[i][1])
            {
                int temp = freq[i][0];
                int temp2 = freq[i][1];
                freq[i][0] = freq[i][1] = 1000000000;
                dp[m][n][state] = max(letsee(m-temp, n-temp2, len, i+1)+1, dp[m][n][state]);
                freq[i][0] = temp; 
                freq[i][1] = temp2;
            }
        }
        if(dp[m][n][state] == -1)dp[m][n][state] = 0;
        // if(dp[m][n][state] == 5)return 4;
        return dp[m][n][state];
    }
};
Теги dynamic programming

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский t3rminated 2017-01-20 13:47:32 1767 Initial revision (published)