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);
}
};
Integer overflow ?
I'm assuming you're trying to store
dp[i][j]
withi
being the index of the type andj
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 alldp[m][j-k*x]
. Here x goes from 0 to count(i) and m goes from 0 to i — 1.