动态规划

动态规划的理论基础

动态规划 Dynamic Programming（DP）：若果一个问题有很多重叠的子问题，使用动态规划是最有效的。

动态规划中的每一个状态是由上一个状态推导出来的，这一点就有别于贪心，贪心是没有推导状态，直接从局部选最优的

动态规划的解题步骤

  • 确定dp数组以及其下标的含义
  • 确定递推公式（转移状态公式）
  • dp数组如何初始化
  • 确定遍历顺序
  • 举例推导dp数组

动态规划如何debug

找问题的最好方式就是把dp数组打印出来，看看究竟是不是按照自己思路推导的！

一些同学对于dp的学习是黑盒的状态，就是不清楚dp数组的含义，不懂为什么这么初始化，递推公式背下来了，遍历顺序靠习惯就是这么写的，然后一鼓作气写出代码，如果代码能通过万事大吉，通过不了的话就凭感觉改一改。

这是一个很不好的习惯！

做动规的题目，写代码之前一定要把状态转移在dp数组的上具体情况模拟一遍，心中有数，确定最后推出的是想要的结果。

然后再写代码，如果代码没通过就打印dp数组，看看是不是和自己预先推导的哪里不一样。

如果打印出来和自己预先模拟推导是一样的，那么就是自己的递归公式、初始化或者遍历顺序有问题了。

如果和自己预先模拟推导的不一样，那么就是代码实现细节有问题。

这样才是一个完整的思考过程，而不是一旦代码出问题，就毫无头绪的东改改西改改，最后过不了，或者说是稀里糊涂的过了。

这也是我为什么在动规五步曲里强调推导dp数组的重要性。

509.斐波那契数列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int fib(int n) {
        if (n < 2) {
            return n;
        }
        int dp[] = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}

70.爬楼梯

假设你正在爬楼梯。需要 n阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

分析：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//分析：因为每次只能上一节台阶或者是两节台阶，
//所以楼梯的个数可以由前两节楼梯的个数所决定的，所以转移状态公式就位
//dp[i] = dp[i-1]+dp[i-2]
class Solution {
    public int climbStairs(int n) {
        int[] dp = new int[n + 2];
        dp[1] = 1; // 表示上第一节台阶只有一种方法
        dp[2] = 2; // 表示上两节台阶有两种方法
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}

从dp[0]=1设置也可以的，下面的i就要从2开始了，本质上是你怎么理解dp[0]，dp[1]的含义了

746.使用最小的花费爬楼梯

dp[i]为使用最小的花费爬楼梯，因为还是一次只能爬一层楼梯或者两层，但是有选择了，cost最小的楼梯

dp[i - 1] 跳到 dp[i] 需要花费 dp[i - 1] + cost[i - 1]。

dp[i - 2] 跳到 dp[i] 需要花费 dp[i - 2] + cost[i - 2]。

那么究竟是选从dp[i - 1]跳还是从dp[i - 2]跳呢？

一定是选最小的，所以dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);

因为你可以选择从下标为 0或下标为 1 的台阶开始爬楼梯。

初始化dp[0] 表示上到第0层需要的最小花费，为0

dp[1]为上到第1层的最小花费，为 0

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 0;
        for (int i = 2; i <= n; i++) {
            dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }
        return dp[n];
    }
}