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.
1import java.util.Arrays;
2
3public class CoinChange {
4 public int change(int amount, int[] coins) {
In Java, we utilize 2D arrays initialized to zero, except for the base case where any denomination, including zero coins, making the amount zero, is set to `1`. The iteration handles all possibilities for adding a specific coin to reach the required amount.
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.