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.
#include <iostream>
using namespace std;
int change(int amount, vector<int>& coins) {
vector<int> dp(amount + 1, 0);
dp[0] = 1;
for (size_t i = 0; i < coins.size(); i++) {
for (int j = coins[i]; j <= amount; j++) {
dp[j] += dp[j - coins[i]];
}
}
return dp[amount];
}
int main() {
vector<int> coins = {1, 2, 5};
int amount = 5;
cout << "Number of combinations: " << change(amount, coins) << endl;
return 0;
}Reduction to a 1D array `dp` occurs in the C++ solution, seamlessly upgrading space efficiency by consolidating state solutions as soon as possible while iteratively resolving each sum creation using the current coin.