grid47 Exploring patterns and algorithms
Sep 16, 2024
6 min read
Solution to LeetCode 518: Coin Change II Problem
Given a set of coins of different denominations, determine how many distinct combinations of these coins sum up to the target amount.
Problem
Approach
Steps
Complexity
Input: You are given an array `coins` containing different coin denominations and an integer `amount` representing the target sum.
Example: amount = 8, coins = [3, 4, 5]
Constraints:
• 1 <= coins.length <= 300
• 1 <= coins[i] <= 5000
• All values in coins are unique
• 0 <= amount <= 5000
Output: The output should be an integer representing the number of distinct combinations of coins that can sum up to the target amount.
Example: 3
Constraints:
• The output should be a non-negative integer.
Goal: To calculate the number of distinct combinations that sum up to the target amount.
Steps:
• 1. Use dynamic programming to calculate the number of ways to make each amount up to the target.
• 2. Initialize a DP array where dp[i] stores the number of ways to make amount i.
• 3. For each coin, update the DP array by considering using that coin multiple times.
Goal: The constraints for the input and output of the problem.
Steps:
• 1 <= coins.length <= 300
• 1 <= coins[i] <= 5000
• 0 <= amount <= 5000
Assumptions:
• The `coins` array contains unique values.
• The `amount` is guaranteed to be within the specified range.
• Input: amount = 8, coins = [3, 4, 5]
• Explanation: There are three distinct ways to make up the amount 8 using the coins [3, 4, 5]: 5+3, 4+4, and 3+3+3.
• Input: amount = 6, coins = [2, 5]
• Explanation: There is only one way to make the amount 6: 2+2+2.
Approach: The solution uses dynamic programming to count the number of ways to make the target amount.
Observations:
• The problem can be solved using dynamic programming as it is a variant of the coin change problem.
• We need to maintain a DP table to track the number of ways to make each possible amount.
Steps:
• 1. Initialize a DP array `dp` of size (amount + 1) with all elements set to 0, except `dp[0]` which should be 1 (base case).
• 2. Iterate over each coin and for each coin, update the DP table by adding `dp[amount - coin]` to `dp[amount]`.
Empty Inputs:
• If the amount is 0, return 1 as there is one way to make the amount 0 (by not using any coins).
Large Inputs:
• The algorithm should handle cases where the amount is large (up to 5000) efficiently.
Special Values:
• If no combination of coins can form the amount, return 0.
Constraints:
• Ensure the solution handles cases where the amount is 0 correctly.
int memo[5001][301];
vector<int> nums;
intdp(int amnt, int idx) {
if(idx == nums.size()) return amnt ==0;
if(memo[amnt][idx] !=-1) return memo[amnt][idx];
// cout << amnt << " " << idx << " " << nums[idx]<< "\n";
int res = dp(amnt, idx +1);
if(amnt >= nums[idx])
res += dp(amnt - nums[idx], idx);
return memo[amnt][idx] = res;
}
staticboolcmp(int a, int b) {
return b < a;
}
intchange(int amount, vector<int>& coins) {
this->nums = coins;
sort(nums.begin(), nums.end(), cmp);
memset(memo, -1, sizeof(memo));
return dp(amount, 0);
}
1 : Variable Initialization
int memo[5001][301];
This initializes a 2D array `memo` that will store the results of subproblems, where `memo[amnt][idx]` represents the number of ways to make the amount `amnt` from the first `idx` coins.
2 : Variable Initialization
vector<int> nums;
This declares a vector `nums` to hold the coins available to make the desired amount.
3 : Function Definition
intdp(int amnt, int idx) {
This is the recursive function `dp` which calculates the number of ways to make the amount `amnt` starting from coin index `idx`.
4 : Base Case
if(idx == nums.size()) return amnt ==0;
If all coins have been considered (`idx` reaches the size of `nums`), return `1` if the remaining amount is zero, otherwise `0`.
5 : Memoization Check
if(memo[amnt][idx] !=-1) return memo[amnt][idx];
Check if the subproblem has already been computed by checking the `memo` table.
6 : Recursion
int res = dp(amnt, idx +1);
Recursively call `dp` to calculate the number of ways to make the amount `amnt` without using the current coin (`idx + 1`).
7 : Recursion with Coin Inclusion
if(amnt >= nums[idx]) res += dp(amnt - nums[idx], idx);
If the current coin can be used (i.e., `amnt >= nums[idx]`), recursively call `dp` including the current coin and subtract its value from `amnt`.
8 : Memoization
return memo[amnt][idx] = res;
Store the computed result in `memo[amnt][idx]` to avoid redundant calculations in future calls.
9 : Static Function
staticboolcmp(int a, int b) {
This is a static comparator function used to sort the coins in descending order.
10 : Static Function
return b < a;
The comparator function sorts coins in descending order to prioritize larger coins first.
11 : Main Function
intchange(int amount, vector<int>& coins) {
This is the main function where the coin change problem is solved using the `dp` function.
12 : Variable Assignment
this->nums = coins;
Assign the `coins` vector to the class member `nums`.
13 : Sorting
sort(nums.begin(), nums.end(), cmp);
Sort the coins in descending order using the `cmp` function.
14 : Memo Initialization
memset(memo, -1, sizeof(memo));
Initialize the `memo` table to `-1` to indicate that no subproblems have been solved yet.
15 : Recursive Call
returndp(amount, 0);
Start the recursive `dp` function from the first coin (`idx = 0`) with the given `amount`.
Best Case: O(n * amount)
Average Case: O(n * amount)
Worst Case: O(n * amount)
Description: The time complexity is O(n * amount), where n is the number of coins and amount is the target sum.
Best Case: O(amount)
Worst Case: O(amount)
Description: The space complexity is O(amount) due to the DP array storing the number of combinations for each amount.
