动态规划

动态规划

什么是动态规划？

动态规划和递归？

斐波那契数列，递归解法是 顶向下 进行 递归 求解；更常见的动态规划代码是 自底向上 进行 递推 求解

1. 自顶向下

是从上向下延伸，都是从一个规模较大的原问题比如说 f(20)，向下逐渐分解规模，直到 f(1) 和 f(2) 这两个 base case，然后逐层返回答案，这就叫「自顶向下」。

1. 自底向上

我们直接从最底下、最简单、问题规模最小、已知结果的 f(1) 和 f(2)（base case）开始往上推，直到推到我们想要的答案 f(20)。这就是「递推」的思路，这也是动态规划一般都脱离了递归，而是由循环迭代完成计算的原因。

动态规划算法题

股票买卖问题

• 一个方法团灭 LEETCODE 股票买卖问题
• 股票问题系列通解（转载翻译）

509. 斐波那契数 easy

题目

斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。 1，1，2，3，5，8，13，21，34，55，89..

解法 1：暴力递归

public static int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

时间复杂度
递归算法的时间复杂度怎么计算？就是用子问题个数乘以解决一个子问题需要的时间。首先计算子问题个数，即递归树中节点的总数。显然二叉树节点总数为指数级别，所以子问题个数为 O(2^n)。然后计算解决一个子问题的时间，在本算法中，没有循环，只有 f(n - 1) + f(n - 2) 一个加法操作，时间为 O(1)。所以，这个算法的时间复杂度为二者相乘，即 O(2^n)，指数级别，爆炸
存在大量重复子问题
存在了大量的计算，f(20) = f(19) + f(18)，f(18) = f(17) + f(16)，f(17) = f(16) + f(15)，可以发现在计算 f(20) 的时候已经计算了 f(18)，而后续 f(18) 又被计算了一遍

解法 2：递归 + 备忘录

思路

1. 用一个备忘录 memo 来计算每次计算的子问题的结果，备忘录一般用数组或哈希表来承担
2. 在计算子问题时，先从 memo 中查找是否有值，如果有值就返回；如果没值递归调用，先不用返回，先记录到备忘录中，再返回

public static int fib(int n) {
    int[] memo = new int[n + 1];
    return helper(memo, n);
}

private static int helper(int[] memo, int n) {
    if (n <= 1) return n;
    if (memo[n] != 0) {
        return memo[n];
    }
    int r = helper(memo, n - 1) + helper(memo, n - 2);
    memo[n] = r;
    return r;
}

时间复杂度 O(n)

子问题个数，即图中节点的总数，由于本算法不存在冗余计算，子问题就是 f(1), f(2), f(3) … f(20)，数量和输入规模 n = 20 成正比，所以子问题个数为 O(n)。解决一个子问题的时间，同上，没有什么循环，时间为 O(1)。

解法 3：动态规划

思路

1. 用一个 dp 数组记录计算的过程，从底向上，先计算 dp[0] 和 dp[1]
2. dp[n] = dp[n-1] + dp[n-2]
3. 最后返回 dp[n] 即可

代码

public static int fib(int n) {
    if (n <= 1) return n;
    int[] dp = new int[n + 1];
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) { // 不能是i<n，否则i=2就不会参与计算了，后续的值也就计算不出来了
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

解法 4（最优解）：动态规划 + 有限的 dp table

根据斐波那契数列的状态转移方程，当前状态只和之前的两个状态有关，其实并不需要那么长的一个 DP table 来存储所有的状态，只要想办法存储之前的两个状态就行了。
可以将空间复杂度降为 O(1)

public static int fib4(int n) {
    if (n <= 1) return n;
    int dp0 = 0;
    int dp1 = 1;
    for (int i = 2; i <= n; i++) { // 不能是i<n，否则i=2就不会参与计算了，后续的值也就计算不出来了
        int dp = dp0 + dp1;
        dp0 = dp1;
        dp1 = dp;
    }
    return dp1;
}

爬楼梯问题

题目：

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？ 输入：n = 3 输出：3 解释：有三种方法可以爬到楼顶。

1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

递归法

思路

1. 可采用递归思路来解决
2. 假设当前位于第 n 阶，那么上一步可能在第 n-1 或者第 n-2 阶，分别需要爬 1 级台阶和 2 级台阶。

那么，f(n) = f(n-1) + f(n-2)，有这个式子我们就可以 dfs 暴力了，但别忘了递归边界。

1. 递归边界： 式子中最小为 n-2 ，根据题意 n-2 >= 0（也可以严格大于 0，区别不大，后面相应修改） ，那么 n >= 2。意味着最后一次递归调用为 f(2) = f(1) + f(0)，边界就是 f(1) = 1，f(0) = 1。

代码

public int climbStairs(int n) {
    if (n <= 2) return n;
    return climbStairs(n - 1) + climbStairs(n - 2);
}

leetcode 过不去，超时了
递归记忆版
记忆化递归，记录递归计算的过程，防止重复计算

public int climbStairs(int n) {
    int[] memo = new int[n + 1]; // 最大索引为 n，因此数组大小需要 n + 1
    for (int i = 0; i < memo.length; i++) {
        memo[i] = -1;
    }
    return climbStairs22(n, memo);
}

public int climbStairs22(int n, int[] memo) {
    if (n <= 2) return n;
    if (memo[n] != -1) {
        return memo[n];
    }
    memo[n] = climbStairs(n - 1) + climbStairs(n - 2);
    return memo[n];
}

斐波那契数列

爬楼梯问题就是个斐波那契数列

public static int climbStairs(int n) {
    int a = 0, b = 1, sum = 0;
    for (int i = 0; i < n; i++) {
        sum = (a + b) % 1000000007; // 这个数字是10位的最小质数，只是数字太大溢出了，需要将计算结果 % 1000000007才能保证得出的结果在int 范围中；
        a = b;
        b = sum;
    }
    return sum;
}

动态规划

思路
爬第 n 阶楼梯的方法数量，等于 2 部分之和：

1. 爬上 n-1 阶楼梯的方法数量。因为再爬 1 阶就能到第 n 阶
2. 爬上 n-2 阶楼梯的方法数量，因为再爬 2 阶就能到第 n 阶

所以我们得到公式 dp[n] = dp[n-1] + dp[n-2]
同时需要初始化 dp[0]=1 和 dp[1]=1
时间复杂度：O(n)
代码

public static int climbStairs(int n) {
    int[] dp = new int[n + 1];
    dp[0] = 1;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

322. 零钱兑换 medium

题目

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。 你可以认为每种硬币的数量是无限的。

解法 1：暴力递归 超过时间限制

public int coinChange(int[] coins, int amount) {
    // base case
    if (amount == 0) return 0;
    if (amount < 0) return -1;

    int result = Integer.MAX_VALUE;
    for (int coin : coins) {
        // 计算子问题
        int subProblem = coinChange(coins, amount - coin);
        if (subProblem == -1) continue;
        result = Math.min(result, subProblem + 1);
    }
    return result == Integer.MAX_VALUE ? -1 : result;
}

优化版：加上备忘录

int coinChange(int[] coins, int amount) {
    int[] memo = new int[amount + 1];
    // 备忘录初始化为一个不会被取到的特殊值，代表还未被计算
    Arrays.fill(memo, -666);
    return dp(coins, amount);
}

int dp(int[] coins, int amount) {
    if (amount == 0) return 0;
    if (amount < 0) return -1;
    // 查备忘录，防止重复计算
    if (memo[amount] != -666)
        return memo[amount];

    int res = Integer.MAX_VALUE;
    for (int coin : coins) {
        // 计算子问题的结果
        int subProblem = dp(coins, amount - coin);
        // 子问题无解则跳过
        if (subProblem == -1) continue;
        // 在子问题中选择最优解，然后加一
        res = Math.min(res, subProblem + 1);
    }
    // 把计算结果存入备忘录
    memo[amount] = (res == Integer.MAX_VALUE) ? -1 : res;
    return memo[amount];
}

解法 2：dp table 迭代 没看懂

https://labuladong.github.io/algo/1/7/

int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    // 数组大小为 amount + 1，初始值也为 amount + 1
    Arrays.fill(dp, amount + 1);

    // base case
    dp[0] = 0;
    // 外层 for 循环在遍历所有状态的所有取值
    for (int i = 0; i < dp.length; i++) {
        // 内层 for 循环在求所有选择的最小值
        for (int coin : coins) {
            // 子问题无解，跳过
            if (i - coin < 0) {
                continue;
            }
            dp[i] = Math.min(dp[i], 1 + dp[i - coin]);
        }
    }
    return (dp[amount] == amount + 1) ? -1 : dp[amount];
}