1. initial approach
- a greedy approach first comes to mind, where we greedily select the largest element in the list that is within the range of the current accumulated value and the target value
- this will not work as greedily choosing the largest elements can create impossible scenarios where there are possibilities with difference combinations
2. intuitive approach
we can break the problem down into a decision tree
where we start from 11, and try and progressively reduce the value to 0
each 'node' in the tree has n possibility (where n is the different coins in the array)
subtract each coin from the current value and continue down the tree until we reach zero
the number of levels traversed (or recursed) is the number of coins used
we keep track of the minimum levels traversed, pruning branches each time they exceed our current min number of coins
if decision line results in the value being less than zero, prune it also and return INT_MAX (to say its invalid)
- this is intuitively correct, but is computationally complex as we are essentially computing every combination of coins and returning the minimum number of coins used to get our value amount
- even with pruning it probably isnt efficient enough
🤔What Did I Struggle With?
~
💡 Explanation of Solution
Top-Down Dynamic Programming with Memoization (caching)
- continuing on from the intuitive approach, if we were to visualise the decision tree, you can see that we are recalculating the minimum number of coins to achieve value x across multiple areas of the problem
- we can use a dp array to store (cache) the minimum number of coins needed to get the values 0 - amount
- this will avoid / prevent repeated computation since we have identified that by doing this decision tree approach, we can see that the subproblems are recurring across different branches
Base Case: zero coins are needed to make amount 0
Recurrence Relation:
- for each coin, recursively compute the minimum coins required for `amount - coin`
- use dp to store intermediate results to avoid redundant computations
Pruning: if the amount is < 0 , return -1
- if dp[amount] is already computed (doesnt have a value of INT_MAX), return it directly to avoid unecessary recursion
Result:
- after processing, dp[amount] contains the minimum number of coins needed, or -1 if it cannot be found
⌛ Complexity Analysis
Time Complexity: O(n * A)
let n = number of coins, a = amount
there are A distinct states, and for each state, we loop over n coins
Space Complexity: O(A)
dp array is of size A+1
recursion stack has a worst case depth of A (if the algorithm has to reduce the amount by 1 repeatedly)
💻 Implementation of Solution
class Solution {private: int helper(vector<int>& coins, int amount, vector<int>& dp) { if(amount < 0) return -1; // invalid amount if(dp[amount] != INT_MAX) return dp[amount]; // use cached result int minCoins = INT_MAX; // init minCoins to find current amount to max for(int coin : coins) { int res = helper(coins, amount - coin, dp); // recursive call if(res != -1) minCoins = min(minCoins, res + 1); // add +1 to our result to account for the current depth we are at } dp[amount] = (minCoins == INT_MAX) ? -1 : minCoins; return dp[amount]; }public: int coinChange(vector<int>& coins, int amount) { // create dp array to store min coins for each amount vector<int> dp(amount + 1, INT_MAX); dp[0] = 0; // base case: 0 coins to reach amount 0 return helper(coins, amount, dp); }};