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.
1#include <stdio.h>
2
3int change(int amount, int* coins, int coinsSize) {
4 int dp[coinsSize + 1][
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).
Time Complexity: O(n*m), Space Complexity: O(n) where `n` is the `amount` and `m` is the number of coins.
public class CoinChange {
public int Change(int amount, int[] coins) {
int[] dp = new int[amount + 1];
dp[0] = 1;
for (int i = 0; i < coins.Length; i++) {
for (int j = coins[i]; j <= amount; j++) {
dp[j] += dp[j - coins[i]];
}
}
return dp[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));
}
}Using a single-dimensional `dp` array in C# ensures that past state solutions are preserved while reducing unnecessary overhead, directing changes and coin allocations smoothly through every iteration.