Sponsored
Sponsored
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).
Time Complexity: O(n*m), Space Complexity: O(n*m) where `n` is the `amount` and `m` is the number of coins.
1using System;
2
3public class CoinChange {
4 public int Change(int amount, int[] coins) {
5 int[,] dp = new int[coins.Length + 1, amount + 1];
6 for (int i = 0; i <= coins.Length; i++) {
7 dp[i, 0] = 1;
8 }
9 for (int i = 1; i <= coins.Length; i++) {
10 for (int j = 1; j <= amount; j++) {
11 dp[i, j] = dp[i - 1, j];
12 if (j >= coins[i - 1]) {
13 dp[i, j] += dp[i, j - coins[i - 1]];
}
}
}
return dp[coins.Length, amount];
}
public static void Main(string[] args) {
CoinChange cc = new CoinChange();
int[] coins = { 1, 2, 5 };
int amount = 5;
Console.WriteLine("Number of combinations: " + cc.Change(amount, coins));
}
}For C#, a 2D array double precision table aids in dynamically computing solutions to subproblems based on the coin additions and respective amounts, stored optimally during iteration.
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).
Time Complexity: O(n*m), Space Complexity: O(n) where `n` is the `amount` and `m` is the number of coins.
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.