322. Coin Change

📝 Problem Details

• Title: 322. Coin Change
• Link: https://leetcode.com/problems/coin-change/
• Difficulty: Medium
• Tags/Categories: Dynamic-Programming

Already Solved, see ⇒ 322. Coin Change

input array coins return the fewest number of coins that are needed to make up the target amount

💭What Were My Initial Thoughts?

- "return fewest x to achieve y" indicates knapsack problem
- since we have infinite number of each coin type, this resembles an unbounded knapsack problem

1. subproblem identification:
	- the number of coins to takes to achieve a number can be used for future computation of larger values

2. top-down vs bottom-up
	- can be achieved with both
	- will attempt to build a bottom-up iterative solution

3. dp state
	- let dp[i] be the min number of coins it takes to achieve target i
	- the dp table will contain 1-n where n is the target
	- if its impossible to achieve that number, store -1 in the table

	For each amount `i`, we try every coin `c`:
	
	1. If i - c ≥ 0, we can form i by using that coin c
	2. Thus, we take the minimum between:
	    - dp[i] (previous computed value).
	    - dp[i - c] + 1 (using c reduces i to i - c, so we need 1 extra coin)

3. state transition
	- to achieve target, starting from 0 we can choose one of the elements from the array, resulting in target-choice left
	- dp[i] = min(dp[i], dp[i - coin] + 1);

💡 Explanation of Solution

same as initial thoughts

⌛ Complexity Analysis

Time Complexity: O(n*m)
- n --> amount
- m --> number of coins

Space Complexity: O(n)
- dp table for number of coins to reach n amounts

💻 Implementation of Solution

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount + 1, INT_MAX); // init dp table
        dp[0] = 0; // base case: 0 coins needed for amount 0
 
        for(int i=1; i <= amount; i++) {
            for(int coin : coins) { // try using each coin
                if(i-coin >= 0 && dp[i-coin] != INT_MAX) { // valid case
                    dp[i] = min(dp[i], dp[i-coin] + 1);
                }
            }
        }
        return (dp[amount] == INT_MAX) ? -1 : dp[amount]; // If no solution, return -1
    }
};