labuladong刷题——第二章（1） 动态规划解题套路框架

一、斐波那契数列

没啥好说的，简单dp，备忘录。

 
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int fib(int n) {
        if(n==0||n==1) return n;
        int dp[] = new int[n+1];
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i < dp.length; i++) {
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }
}
//leetcode submit region end(Prohibit modification and deletion)

唯一一个需要注意的点就是int[n+1]，比如说是10，那么int[10]就是从0-9，只是代表有十个数字，而斐波那契数列要求的是10，所以是n+1。

---

二、凑零钱问题

import java.util.Arrays;
 
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int coinChange(int[] coins, int amount) {
        int dp[] = new int[amount+1];
        Arrays.fill(dp, amount+1);
        dp[0] = 0;
        for (int i = 1; i < dp.length; i++) {
            for (int coin : coins) {
                if (i - coin < 0) continue;
            // 说明子问题有解
            // 比如说4，对于5元而言就是误解的
            // 但是同样的,对于1元而言,就是有解的,开始计算
            dp[i] = Math.min(dp[i], 1 + dp[i - coin]);
            }
        }
        return (dp[amount]==amount+1)? -1:dp[amount];
    }
}
//leetcode submit region end(Prohibit modification and deletion)

 其实想到了也很好理解。

同样是使用备忘录问题，最难想到的是dp数组的定义。

这里我们用当目标金额为 i 时，至少需要 dp[i] 枚硬币凑出，这样最后的结果就是dp[amount]这个数了。

构造的方法也很简单：比如对于硬币1 2 5 而言：dp[8]，就是从dp[8-1] dp[8-2] dp[8-5]之间选一个最小+1就可以，代表着之前三个数多一个面值不同的硬币。

如果是dp[4]，那么就没有用5这个硬币的可能性，直接跳过即可。

多提一句找零钱2 LC518

 这其实是个背包问题——某个重量的背包该用多少不同的物品放进去，总共有多少种方式？

难点在于DP数组的设计。

对比背包问题，可以把dp设计成dp[i][j]为用前i种不同的物品放满 j 空间背包的数组

 
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int change(int amount, int[] coins) {
        int n = coins.length;
        int[][] dp = new int[n + 1][amount + 1];
        // 这里这么定义的原因是
        // 本质背包问题
        // dp[i][j]的含义是：用前i种硬币装总共j的金额的方法数
        // 比如dp[2][3]而言 就是用前两种硬币凑出三元的方法数
        // 而dp[3][3]而言 就是用前三种硬币凑出三元的方法数
        // 这么一看突然发现，dp[3][3]至少等于dp[2][3]——最后一个不用就行了！
        // 同时 比如dp[3][3]而言 不仅要算上dp[2][3] 还要算上用上最后一种的
        // 也就是说，同时还要算上dp[3][总重量-刨去第三种物品的总重量]的数量
        // 用三种不同的物品，并且刨去第三种总重量物品的种类，注意二者的值是一样的。
        for (int i = 0; i <= n; i++)
            dp[i][0] = 1;
        // 初始化 也就是说，凑出0块钱，用任何硬币都只有一种方法：就是不放！
        for (int i = 1; i < n+1; i++) {
            for (int j = 1; j < amount+1; j++) {
                if(j - coins[i-1]>=0) {
                    //说明有两种凑的方法
                    // 比如前面有两种硬币 加入第三种硬币的话
                    dp[i][j] = dp[i-1][j] + dp[i][j - coins[i-1]];
                } else {
                    dp[i][j] = dp[i-1][j];
                }
            }
 
        }
        return dp[n][amount];
    }
}
 
//leetcode submit region end(Prohibit modification and deletion)