# Knapsack problem

###### tags: `Steven` `DP`

# 0/1

# 有限

# 無限

## [322. Coin Change](https://leetcode.com/problems/coin-change/)

### top-down

#### TLE

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        if(amount == 0) {
            return 0;
        }
        
        int mn = INT_MAX;
        for(const auto &coin : coins) {
            if(amount - coin >= 0) {
                int ret = coinChange(coins, amount - coin);
                if(ret == -1)
                    continue;
                
                mn = min(mn, ret);
            }
        }
        
        return mn == INT_MAX ? -1 : mn + 1;
    }
};

#### With Memoization

#include <bits/stdc++.h>
using namespace std;

class Solution
{
private:
    int cache[10001];
    int go(vector<int> &coins, int amount)
    {
        if (amount == 0) {
            return 0;
        }

        if (cache[amount] != 0x3f3f3f3f) {
            return cache[amount];
        }

        int mn = INT_MAX;
        for (const auto &coin : coins) {
            if (amount - coin >= 0) {
                int ret = go(coins, amount - coin);
                if (ret == -1)
                    continue;
                mn = min(mn, ret);
            }
        }

        cache[amount] = mn == INT_MAX ? -1 : mn + 1;

        return cache[amount];
    }

public:
    int coinChange(vector<int> &coins, int amount)
    {
        memset(cache, 0x3f, sizeof(cache)); 
        return go(coins, amount);
    }
};

##### My stupid bug ...

class Solution {
private: 
    int cache[10001];
    int go(vector<int>& coins, int amount) {
        if(amount == 0) {
            return 0;
        }
                
        if(cache[amount] != 0) {
            return cache[amount];
        }
        
        int mn = INT_MAX;
        for(const auto &coin : coins) {
            if(amount - coin >= 0) {
                int ret = coinChange(coins, amount - coin); // bro... calling the wrong function lol
                if(ret == -1)
                    continue;
                mn = min(mn, ret);
            }
        }
        
        cache[amount] = mn == INT_MAX ? -1 : mn + 1;
        
        return cache[amount];
    }
public:
    int coinChange(vector<int>& coins, int amount) {
        memset(cache, 0x3f, sizeof(cache)); // no wonder this memset thing will cause timeout lol
        return go(coins, amount); 
    }
};

### bottom-up

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        // 無限背包
        int dp[amount + 1];
        memset(dp, 0x3f, sizeof(dp));
        
        dp[0] = 1; // base condition
        
        for(const auto &coin : coins) {
            for(int i = 0; i + coin <= amount; i++) {
                if(dp[i] > 0) {
                    dp[i + coin] = min(dp[i + coin], dp[i] + 1);
                }
            }
        }
        
        return dp[amount] == 0x3f3f3f3f ? -1 : dp[amount] - 1;
    }
};