watch out for integer overflow :). i had to switch to 64-bit int.

A VERY helpful link for anyone who cannot understand the subproblems involved: http://www.ideserve.co.in/learn/coin-change-problem-number-of-ways-to-make-change

The solution to this problem is a good example of an efficient and tight Dynamic Programming algorithm. For those of you who are struggling with it, here's a tip. The number of ways you can make change for n using only the first m coins can be calculated using:

(1) the number of ways you can make change for n using only the first m-1 coins.

(2) the number of ways you can make change for n-C[m] using the first m coins (where C is the array of coins).

This data allows you to build the recurrence relation.

Keeping it simple :D

n, m = map(int,input().split())
coins = list(map(int,input().split()))
dp = [1]+[0]*n
for i in range(m): 
    for j in range(coins[i], n+1): dp[j]+=dp[j-coins[i]]
print(dp[-1])

For someone new to coding, this is a very interesting question and I def learned quite a lot from it. I'm writing this post just to help myself remember it.

The core concept is:

calculator(coins, numToUse, sum) = calculator(coins, numToUse-1, sum) + calculator(coins, numToUse, sum-coins[numToUse-1]); basically saying for the current sum, it can and only can be achieved by two sub-cases:

(1). you use one less kind of coins, and still achevie this sum.

(2). you still use the same set of coins, but achieve (sum-oneCoinValue). This "oneCoinValue" is the value of the coin that you eliminates in the sub-case (1) And if you total these two cases up, you get what you want.

And the next step is to speed up your program. If you think about it, there are some potential redundent calculations-- for a lot of sub-cases, they ended up trying to calculate the same sum. And here, I made my first improvement, and it FAILED hardcore... i used an array of size sum, as a look up table. Have I calculated the current sum already, if so, don't do the recursive call, but return the value that was already saved in the table; if not do the recursive call, and save the final return value to the lookup table.

Apparently, that approach did NOT end up well. I couldn't even get the first two mini test cases passed. And then I realized, apparently, there are two important arguments that are passed in: sum AND the numToUse, which basically tells you how many types of coins that you are allowed to use to get the sum. So if you only use a one dimentioanl array to save the result, that's not enough. Using coins {1,2,3} to achieve the number 10 of course is not going to be the same as if you only allowed to use coins {1,2}. The lookup table needs to be 2D. And the major calculator function look like this:

private static long calculator(int[] coins, int numToUse, int sum){

    if( sum ==0 ){
        return 1;
    }

    else if(sum < 0 ){
        return 0;
    }
    else if (numToUse <= 0){
        return 0;
    }
    else {
        if (done[sum][numToUse] == -7){
           done[sum][numToUse] =  calculator(coins, numToUse-1, sum) + calculator(coins, numToUse, sum-coins[numToUse-1]) ;
        }
       return done[sum][numToUse];
    }
}


// -7 is just the value that I intialize the array done, I picked it becuase I like number 7, haha