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 <vector>
2#include <iostream>
3using namespace std;
4
5int change(int amount, vector<int>& coins) {
6 vector<vector<int>> dp(coins.size() + 1, vector<int>(amount + 1, 0));
7 for (int i = 0; i <= coins.size(); i++) {
8 dp[i][0] = 1;
9 }
10 for (size_t i = 1; i <= coins.size(); i++) {
11 for (int j = 1; j <= amount; j++) {
12 dp[i][j] = dp[i-1][j];
13 if (j >= coins[i-1]) {
14 dp[i][j] += dp[i][j - coins[i-1]];
}
}
}
return dp[coins.size()][amount];
}
int main() {
vector<int> coins = {1, 2, 5};
int amount = 5;
cout << "Number of combinations: " << change(amount, coins) << endl;
return 0;
}The C++ version utilizes the vector library to manage a 2D dynamic programming table, which helps in storing results for subproblems. It aims at reducing redundancy by retaining past calculations for sum combinations.
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.