Coin Change II - Solution & Explanation

This method involves using a 2D array to keep track of number of ways to make up a certain amount using coins up to a particular denomination. The rows in the array represent the number of coins available (up to that index), and the columns represent each possible amount up to the target.

Define dp[i][j] as the number of ways to make amount j using the first i types of coins. Initialize dp[i][0] to 1 since there is one way to make amount 0 (choosing no coin). For each coin, iterate over all amounts and accumulate the number of ways by including the current coin.

Time complexity is O(n*m) where n is the amount and m is the number of coins. Space complexity is also O(n*m).

In the C implementation, we define a 2D array `dp` to represent the number of ways to achieve each possible amount (0 to `amount`) using the coins up to the current denomination. We iterate through every possible amount for each coin type, keeping the previously computed results.

This method optimizes space usage by employing a 1D array to store results. It iterates over each coin and updates the number of ways for each possible amount.

Define dp[j] as the number of ways to make amount j. Initially, set dp[0] to 1 (to denote the empty set that sums up to zero). Iterate through each coin, then iterate over possible amounts in nested for-loops from current coin's value to amount, updating the dp array by adding ways from previous calculations.

Time complexity remains O(n*m), but space complexity improves to O(n).

The C representation here manages a 1D array `dp` after consolidating lesser used states, promoting space efficiency while preserving the calculated subproblems on a single line at every stage of iteration.