322. Coin Change.md

LeetCode 322. Coin Change

动态规划

1. 最优子结构： 可以通过求解子问题来求原问题，子问题之间相互独立，且存在重叠子问题

2. 先写暴力遍历（穷举搜索），DP可以看成是对穷举搜索的优化/剪枝

3. base case: amount = 0时， 返回0

4. 状态（原问题和子问题都在变化的量）， amount

5. 选择（导致状态发生变化的量）， 选择不同的面值

6. dp函数或者dp table： 输入——状态 amount， 输出——结果，最少的硬币数

   dp[i] 表示总额为i时的最少的硬币数量

框架

# base case
dp[0] = 0
# 状态转换方程
for (int i = 1; i <= amount; i++) 
{
    // 注意不是所有的情况都成立
		dp[i] = min(1 + dp[i-coin] | for coin in coins)
}
return dp[amount]; // 有不成功的可能性

假设coins数组有k种取值，最大金额amount = n, 时间复杂度: $O(nk)$

class Solution {
    public int coinChange(int[] coins, int amount) { 
        int[] dp = new int[amount+1];
        // base case
        dp[0] = 0;
        // 状态转换
        for (int i = 1; i <= amount; i++) {
            dp[i] = amount + 1;
            for (int coin : coins) {
                if (coin > i) continue;
                dp[i] = Integer.min(dp[i], 1 + dp[i-coin]);
            }
        }
        return (dp[amount] == amount + 1) ? -1 : dp[amount];
    }
}

穷举/暴力搜索

时间复杂度: $O(n^k)*O(k) = O(n^k * k)$

class Solution {
    public int coinChange(int[] coins, int amount) { 
        if (amount < 0) return -1;
        if (amount == 0) return 0;

        int res = amount + 1;
        for (int coin : coins) {
            int tmp = coinChange(coins, amount - coin);
            if (tmp < 0) continue;
            res = Integer.min(res, 1 + tmp);
        }
        return res == amount + 1 ? -1 : res;
    }
}

带备忘录的递归

实际上，带备忘录的递归与DP是异曲同工，只是一个是自顶向下，一个是自底向上。

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] memo = new int[amount+1];
        int init = amount + 1;
        for (int i = 0; i <= amount; i++)
            memo[i] = init;
        return helper(memo, coins, amount, init);
    }
    
    static int helper(int[] memo, int[] coins, int n, int init){
       if (n < 0) return -1;
       if (n == 0) return 0;
       if (memo[n] < init) return memo[n]; // memo[n] has been calculated

        // does not been calculated
        int res = init;
       for (int coin : coins) {
           int tmp = helper(memo, coins, n-coin, init);
           if (tmp < 0)
                continue;
           res = Integer.min(res, 1+tmp);
       }
       memo[n] = res == init ? -1 : res;
       return memo[n];
    }
}