1. Set up: sort the coins in ascending manner.
2. Define state: dp[i][j]: # of ways to get number i, using coins values as largest as the j-th coin. (i.e. the coins chosen to construct number i cannot exceed c[j])

3. State transition: for each coin c[j] and fix to be the next (also largest) coin from the last step (i.e. i-c[j])

   • Starting point: number of ways using c[j] as the largest always >= using the second largest coin c[j-1]

     dp[i][j] = dp[i][j-1]

   • If i no additional ways
   • If i==c[j]: 1 new way in addition to using at largest c[j-1], i.e. using c[j] directly to get number i

     dp[i][j]+=1

   • If i>c[j]: first get i-c[j] in dp[i-c[j]][j] ways, then get i by adding c[j] -> dp[i-c[j]][j] new ways

     dp[i][j] += dp[i-c[j]][j] ** why no duplications? for example, dp[4][] = dp[1][] + dp[3][], without [] specified, dp[1]=1 means (1+3); dp[3]=2 means (1+1+1; 3+1), where (1+3) is double-counted. If when we use a new coin, and make it the largest that can be used, then dp[4-1][1]=1 (i.e. 1+1+1).

4. Edge cases:

   • dp[i][0] = 1 if i%c[0]==0 else 0

def getWays(n, coins):
    coins = sorted(coins)
    print(coins)
    dp=[[0]*len(coins) for i in range(n+1)]
 
    for i in range(1,n+1):
        print("0 : ", dp[0])
        # visited = {c:False for c in coins}
        dp[i][0]=1 if i%coins[0]==0 else 0
        for j in range(1,len(coins)):
            dp[i][j]=dp[i][j-1] 
            if i<coins[j]: 
                continue
            if i==coins[j]:
                dp[i][j]+=1
            dp[i][j]=dp[i][j]+dp[i-coins[j]][j]
        print(i,": ", dp[i])   
    
    return dp[n][len(coins)-1]
    

My super non-slick code. Passed all tests though.

def getWays(n, c): # Write your code here

rows = len(c)
cols = n + 1

dp = [[0 for _ in range(cols)] for _ in range(rows)]

for row in range(rows):
    for col in range(cols):
        if col == 0:
            dp[row][col] = 1
        elif row == 0:
            if col < c[row]:
                dp[row][col] = 0
            else:
                dp[row][col] = dp[row][col-c[row]]
        else:
            if col < c[row]:
                dp[row][col] = dp[row-1][col]
            else:
                dp[row][col] = dp[row-1][col] + dp[row][col-c[row]]

return dp[rows-1][cols-1]

JS Javascript solution passes all tests:

function getWays(n, c) {
    // Write your code here
    const dp = new Array(c.length).fill(new Array(n).fill(0));
    const sorted = c.sort((a,b)=>a-b);
    for (let i = 0; i<sorted.length; i++){
        for(let j=0; j<=n; j++){
        if (j === 0) {
            dp[i][j] = 1;
            continue;
        }
        if (i === 0){
            dp[i][j] = j%sorted[i] === 0 ? 1 : 0;
            continue;
        }
        if (sorted[i] > j) {
            dp[i][j] = dp[i-1][j];
        } else {
            dp[i][j] = dp[i][j-sorted[i]] + dp[i-1][j];
        }
        }
        if (sorted[i]>n) {
        return dp[i][n];
        }
    }
    return dp[sorted.length-1][n];
}

def getWays(n, c):
    count = [0]*(n+1)
    count[0] = 1
    c.sort(reverse = True) 
    for coin in c:
        for i in range(coin, n +1):
            count[i] += count[i-coin]
    return count[n]
		

sorting is done in order to understand how denomination is formed