More standard solution is just based on the simple recursive formula:

*F*(*n*, *S*) = *F*(*n*, *S* - coins[*n*-1]) + *F*(*n*-1, *S*) for *n* > 0, *S* > 0

Corner cases:

*F*(*n*, 0) = 1

*F*(*n*, *S*) = 0 for *S* < 0

*F*(*n*, *S*) = 0 for *n* <= 0, *S* > 0

Then a possible implementation is just two nested for-loops:

- outer loop runs over the number of coins
*n* (0 <= n <= coins.length),
- inner loop runs over all the possible
*S* (0 <= S <= amount).

In this implementation, dp[*n*][*S*] represents *F*(*n*, *S*), where we save the values of *F*.

This implementation uses different and more complicated recursive function. Let's try to obtain it from the definition of *F*(*n*, *S*). Let's apply this function multiple times:

- firstly, for
*F*(*n*, *S*),
- then for
*F*(*n*, *S* - cost[*n*-1]),
- then for
*F*(*n*, *S* - 2 cost[*n*-1]),

and so on, till we get:
*F*(*n*, *S* - *k* cost[*n*-1])

for some maximum *k* such that *S* - *k* cost[*n*-1] is still >= 0, or

0 <= *k* <= *S* / cost[*n*-1]

So basically, we expand *F*(*n*, *S*) many times by applying the recursive function for *F*:

*F*(*n*, *S*) = *F*(*n*, *S* - coins[*n*-1]) + *F*(*n*-1, *S*)

= *F*(*n*, *S* - 2 coins[*n*-1]) + *F*(*n*-1, *S* - coins[*n*-1]) + *F*(*n*-1, *S*)

= *F*(*n*, *S* - 3 coins[*n*-1]) + *F*(*n*-1, *S* - 2 coins[*n*-1]) + *F*(*n*-1, *S* - coins[*n*-1]) + *F*(*n*-1, *S*)

...

= *F*(*n*-1, *S* - *k* coins[*n*-1]) + ... + *F*(*n*-1, *S* - 2 coins[*n*-1]) + *F*(*n*-1, *S* - coins[*n*-1]) + *F*(*n*-1, *S*)

= **sum**( *F*(*n*-1, *S* - *k* coins[*n*-1]), for 0 <= *k* <= *S* / cost[*n*-1] )

So algebraically the initial simple recursive function and the last recursive function with the sum are equal, but the former is simpler and runs faster (using DP, its time complexity is just **O**(coins.length * amount)), while the later is more complicated and runs slower (using DP, it is **O**(coins.length * amount^2) -- 3 nested loops).

You may ask: "What is the reason to make things more complicated?"

Usually there are no so many ones, but may be in this case the author came up directly to the more complicated recursive function and just implemented it without trying to find better solution. In some cases, if there is a simpler solution, one can algebraically transform it to a simple one. This is true for this case as well, having the last recursion, we can apply some transformation and find the simple solution.

May be the author was aware of other solutions but just wanted to share his unique implementation. Anyway I find this approach is not less interesting than others.