动态规则笔记

框架

# 初始化 base case
dp[0][0][...] = base
# 进行状态转移
for 状态1 in 状态1的所有取值：
    for 状态2 in 状态2的所有取值：
        for ...
            dp[状态1][状态2][...] = 求最值(选择1，选择2...)

斐波那契数

class Solution {

    public int fib(int n) {
        if(n == 0 || n==1) {
            return n;
        }
        int answer = 0;
        int last = 1;
        int last_last = 0;
        for(int i=2; i<=n; i++) {
            answer = last + last_last;
            last_last = last;
            last = answer;
        }
        return answer;
    }
}

零钱兑换

题目：
给定不同面额的硬币 coins 和一个总金额 amount。
编写一个函数来计算可以凑成总金额所需的最少的硬币个数。
如果没有任何一种硬币组合能组成总金额，返回 -1。

class Solution {
    Map<Integer, Integer> map = new HashMap<>();


    // 非递归版本
    public int coinChange(int[] coins, int amount) {
        if(amount == 0) {
            return 0;
        }
        int[] arr = new int[amount + 1];
        for(int i=1; i<arr.length; i++) {
            arr[i] = -1;
        }
        for(int coin: coins) {
            if(coin < arr.length) arr[coin] = 1;
        }
        for(int i=1; i<=amount; i++) {
            if(arr[i] != -1) continue;
            int min = i;
            boolean hasAnawer = false;
            for(int coin: coins) {
                if(i-coin < 0) continue;
                if(arr[i-coin] == -1) continue;
                min = Math.min(min, arr[i-coin] + 1);
                hasAnawer = true;
            }
            if(hasAnawer) arr[i] = min;
        }
        return arr[amount];
    }

    // 递归版本
    public int coinChange2(int[] coins, int amount) {
        if(map.containsKey(amount)) return map.get(amount);

        if(amount == 0) {
            map.put(amount, 0);
            return 0;
        }

        if(amount < 0) {
            map.put(amount, -1);
            return -1;
        }

        int min = amount;
        boolean hasAnawer = false;
        for(int coin : coins) {
            if(amount - coin < 0) continue;
            int subAnswer = coinChange(coins, amount - coin);
            if (subAnswer == -1) continue;
            min = Math.min(min, subAnswer + 1);
            hasAnawer = true;
        }
        if (!hasAnawer) min = -1;
        map.put(amount, min);
        return min;
    }
}