i was solving this DP question on leetcode in which we are given an integer array c representing coins of different denominations and an integer x representing a total amount of money and we need to return the number of combinations that make up that amount. If that amount of money cannot be made up by any combination of the coins, return 0.

Also mentioned that you can assume that you have an infinite number of each kind of coin.

I got stuck on the last test case , can someone tell me the error i am committing?

my approach was like this,

class Solution {
public:
    int change(int x, vector<int>& c) {
        int mod=1000000007;
        int n=c.size();
        int dp[n][x+1];
        for(int i=0;i<n;i++){
            for(int s=0;s<=x;s++){
                if(s==0)dp[i][s]=1;
                else{
                    int op1=(c[i]>s)?0:dp[i][s-c[i]];
                    int op2=(i==0)?0:dp[i-1][s];
                    dp[i][s]=(op1+op2)%mod;
                }
            }
        }
        return dp[n-1][x];
    }
};

I am applying the concept of 2D dp here to find the number of ways to get the target value ‘x’.

However my code works for all testcases including-

x = 5

c = [1,2,5]

expected output: 4

x = 3

c = 2

expected output: 0

Except this test case which got stuck.

It has the following parameters-

x = 1000;
c = [3,5,7,8,9,10,11];

my output is: 952879221…
whereas the correct output should be:
1952879228…

The constraints are as follows:

Constraints:

• 1 <= c.length <= 300

• 1 <= c[i] <= 5000

• All the values of c are unique.

• 0 <= x <= 5000

changing datatype of dp array from int to long long too does’nt work.

I think maybe my output misses the first and some values from the last as per the correct answer and i want to know why.