anshu2002's blog

Please help me in debugging the code . I am total noob
By anshu2002, history, 21 month(s) ago, In English

This is was my implementation for previous weekly fourth question what's wrong in my code ?

class Solution {
public:
    vector<vector<int>>dp;
    int solve(int i,vector<vector<int>>&num,int sum){
        if(sum==0)
        {
            return 1;
        }
        if(i==num.size()||sum<0)
            return 0;
        if(dp[i][sum]!=-1)
            return dp[i][sum];
        int ans = 0;
        if(num[i][0]>0)
        {
            num[i][0]--;
            ans+=solve(i,num,sum-num[i][1]);
            ans%=1000000007; 
            num[i][0]++;
        }
        ans+=solve(i+1,num,sum);
        ans%=1000000007;
        return dp[i][sum]=ans;
    }
    int waysToReachTarget(int target, vector<vector<int>>& types) {
        dp = vector<vector<int>>(types.size(),vector<int>(target+1,-1));
        return solve(0,types,target);
    }
};
  • Vote: I like it
  • -16
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Integer overflow ?

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm assuming you're trying to store dp[i][j] with i being the index of the type and j being the local target of the recursion.

Now at every index i, lets say the marks are k. So to fill dp[i][j] you would need the values of all dp[m][j-k*x]. Here x goes from 0 to count(i) and m goes from 0 to i — 1.

Implemented Code
→ Reply