t3rminated's blog

dynamic programming question

By t3rminated, history, 8 years ago, In English

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];
    }
};
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
8 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

Your dp is not well stated. A dp is used whenever the same result is used over and over again. In this case, dp[m][n][state] should represent the same strings being chosen over and over. However, this is not true, because you are crossing states (i.e. for you visiting the first string and then the second is different than visiting the second and then the first). In order to use dp appropriately, you should have a clear visiting order for each of the states. See the following code. We visit the strings in order, from 0 to len - 1.

int letsee(int m, int n, int len, int state)
    {
        if(state==len) return 0; // We have visited all strings in the array.
        if(m == 0 && n == 0) return 0;
        if(m < 0 || n < 0)  // You cannot have m nor n lesser than 0
            return -1;
        if(dp[m][n][state] != -1)
            return dp[m][n][state];

        // If we don't have enough zeros or ones for this item, just ignore it, and get the answer
        // from the next item
        if(m<freq[state][0] || n<freq[state][1])
            return dp[m][n][state]=letsee(m,n,len,state+1);

        dp[m][n][state]=1   // We can at least choose strs[state] to produce.

        // Notice the start of the cycle, it avoids checking the same state
        for(int i = state + 1 ; i < len; i++)
        {
            dp[m][n][state]=max(dp[m][n][state],letsee(m-freq[state][0],n-freq[state][1],len,state+1)+1);
        }

        return dp[m][n][state];
    }

If you have any questions, feel free to ask!

→ Reply