代码随想录day32--动态规划理论基础

什么是动态规划

动态规划简称DP，如果某一问题有很多重叠子问题，使用动态规划是最有效的。

所以动态规划中每一个状态一定是由上一个状态推导出来的，这一点一定要和贪心区别出来，贪心没有状态推导，而是直接从局部直接选择最优。

在贪心中，有一个例子是背包问题。

eg：由N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i]。每件物品只能使用一次，求解将哪些物品装进背包里物品价值总和最大。

动态规划中dp[j]是由dp[j-weight]推导出的，然后取max(dp[j],dp[j-weight[i]+value[i])。

但如果是使用贪心，每次拿物品只会选择一个最大的或者最小的，和之前的状态没有什么关系。所以贪心解决不了动态规划的问题。

大家只需要明白动态规划是由前一个状态推导出来的，而贪心是局部直接选出最优的。

---

动态规划的解题步骤

做动态规划的题目的时候，很多同学包括我自己都有一个误区，就算将状态转移公式背下，然后照葫芦画瓢，然后根据公式进行代码书写，无论题目是否通过，都不清楚我们使用的dp[i]到底有什么用。

状态转移公式（递推公式）是很重要，但是仔细了解过后，或发现，动态规划不仅仅由递推公式。

对于动态规划，将其拆分为以下五部曲，这五步都搞懂，就基本可以把动态规划掌握：

1.确定dp数组以及其下标的含义

2.确定递推公式

3.dp数组如何初始化

4.确定遍历顺序

5.举例推导dp数组

*一定不要忽略初始化，因为一些情况是递推公式决定了dp数组要如何初始化

---

动态规划应该如何debug

绝大部分同学，对于动态规划的题目是，看题解感觉会了，然后照葫芦画瓢，如果能过那就没关系，但是如果没过，那么怎么改都过不去，对于之前说的dp数组的初始化，递推公式，遍历顺序，都是处于一种什么都不明白的的状态。

找到问题的最好办法就是将dp数组打印出来，看看究竟是不是按照自己的思路推导的

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

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

如果打印出和自己预先模拟推导的一样，那么就算自己的递归公式、初始化或者遍历顺序有问题。如何还是不一样，那就是代码实现的细节有问题了。

这才是一个完整的思考过程，而不是代码出现了问题，就毫无头绪的乱改，最后依旧过不了，或者是稀里糊涂的过

从现在开始，写动态规划的题目出现问题或者无法通过，自己可以先思考这三个问题：

1.这道题我距离推导状态公式了吗

2.我们打印dp数组了吗

3.打印出的dp数组和我想的一样吗

如果这三个问题实现了，那么基本上动态规划的题目也就是解决了

亦或者是可以更清晰的明白自己究竟是哪一点不明白，是状态转移不明白，还是具体代码不知道该怎么写，还是不理解遍历dp数组的顺序。这样带着目的性的问题，就很好了。

---

LeetCode509.斐波那契数

题目描述：

斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1

给定 n ，请计算 F(n) 。

示例 1：

输入：n = 2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1

示例 2：

输入：n = 3
输出：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2

示例 3：

输入：n = 4
输出：3
解释：F(4) = F(3) + F(2) = 2 + 1 = 3

解题思路：

·这道题大家再熟悉不过了，但是就是因为这题比较简单，所以大家可能并没有做什么分析，就顺手写过了，我们使用动态规划五部曲进行分析

1.确定dp数组以及下标的含义

dp[i]的定义为：第i个数的斐波那契数值是dp[i]

2.确定递推公式

因为题目已经把递推公式给我们了，所以可以直接使用 dp[i] = dp[i-1] + dp[i-2]

3.dp数组如何初始化

题目中给的也很明确了

dp[0] = 0;dp[1] = 1;

4.确定遍历顺序，从递归公式中我们可以看出dp[i]是依赖dp[i-1]和dp[i-2]，那么遍历顺序，就算一定是从前到后遍历

5.举例推导dp数组

按照递推公式，我们推导一下，当n为10时，数列应该是:0 1 1 2 3 5 8 13 21 34 55

如果最终代码无法通过，我们就将dp数组打印出，观察与我们推导的数列是不是一致的

以上，使用动态规划的方法全部分析完毕，代码如下：

class Solution {
public:
    int fib(int n) {
        if(n <= 1) return n;
        vector<int> dp(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];
    }
};

·时间复杂度:O(n)

·空间复杂度:O(n)

总结：这道题虽然说非常的基础，但是我们严格按照动态规划五部曲进行分析，发现其实分析过程也并不会复杂，我们使用简单题目用于掌握方法，接下来的方法会越来越重要。

LeetCode70.爬楼梯

题目描述：

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

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

示例 1：

输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶

示例 2：

输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

解题思路：

·这题仔细分析，多举几个例子，就会发现其规律。爬一层楼梯有一种方法，爬两层楼梯有两种方法，爬三层楼梯就可以根据前两层的规律进行推导

我们来进行动态规划五部曲的分析：

1.确定dp数组以及下标的含义

dp[i]：爬到第i层楼梯，有dp[i]种方法

2.确定递推公式

这道题怎么样才能推导出dp[i]呢？

从dp[i]的定义可以看出，dp[i]可以有两个方向可以推导出

首先是dp[i-1]，上i-1层楼梯，有dp[i-1]种方法，那么再一步跳一个台阶不就是dp[i]了

dp[i-2]也是一样的思想，有dp[i-2]种方法，那么再一步跳两个个台阶不就是dp[i]了

所以就可以得出结论 dp[i]就算dp[i-1]和dp[i-2]之和

在推导dp[i]的时候，一定要时刻想着dp[i]的定义，这就体现出确定dp数组以及下标的含义的重要性

3.dp数组如何初始化

dp[0] = 1,因为不动也是一种移动方法

dp[1] = 1,只有一步可以走

dp[2]  = 2 ,有一步和两步可以走,所以我们就可以从i=3开始递推

4.确定遍历顺序

从递推公式dp[i] = dp[i-1]+dp[i-2]可以看出,遍历顺序一定是从前向后的

5.举例推导dp数组

我们会发现这个数组推导出来就算斐波那契,如果代码出现问题,那么就把dp数组打印出来,看看是否和自己推导的一样

代码如下:

class Solution {
public:
    int climbStairs(int n) {
        if(n <= 1) return n;
        vector<int> dp(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];
    }
};

 时间复杂度:O(n)

空间复杂度:O(n) 

总结:这道题其实和斐波那契数题目是一样的,但是动态规划五部曲,却比上一题复杂了那么多

关键就算斐波那契题目描述中,已经把递归公式和如何初始化都给出来了,剩下的就很好推出

但是本题需要逐个分析,大家应该初步感受出了动态规划的五部曲了

LeetCode746.使用最小花费爬楼梯

题目描述：

给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

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

请你计算并返回达到楼梯顶部的最低花费。

示例 1：

输入：cost = [10,15,20]
输出：15
解释：你将从下标为 1 的台阶开始。
- 支付 15 ，向上爬两个台阶，到达楼梯顶部。
总花费为 15 。

示例 2：

输入：cost = [1,100,1,1,1,100,1,1,100,1]
输出：6
解释：你将从下标为 0 的台阶开始。
- 支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。
- 支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。
- 支付 1 ，向上爬一个台阶，到达楼梯顶部。
总花费为 6 。

解题思路：

1.确定dp数组以及下标的含义

使用动态规划，需要使用一个数组来记录状态，本题只需要一个一维数组dp[i]就可以了

dp[i]的定义：达到第i个台阶所花费的最少体力为dp[i]

2.对于递推公式

得到dp[i]，需要知道dp[i-1]和dp[i-2]

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

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

按照题目要求，所以我们选择最小的，dp[i] = min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])

3.dp数组如何初始化

看了递推公式，所以我们就可以知道需要初始化dp[i-1]和dp[i-2]，也就是dp[0]dp[1]

题目中说可以选择下标为0或下标为1的台阶开始爬楼梯，也就是说到达第0个台阶和第一个台阶是不花费的，所以dp[0] = dp[1] = 0

4.确定遍历顺序

因为是模拟台阶，而且dp[i]由dp[i-1]和dp[i-2]推出，所以是从前到后遍历cost数组即可\

5.举例推导dp数组

我们使用示例2进行举例

如果代码出现问题，就将dp数组打印出来，看看和如上推导是不是一样的

代码如下：

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        vector<int> dp(cost.size()+1);
        dp[0] = 0;
        dp[1] = 0;
        for(int i = 2;i <= cost.size();i++){
            dp[i] = min(dp[i-2]+cost[i-2],dp[i-1]+cost[i-1]);
        }
        return dp[cost.size()];
    }
};

·时间复杂度:O(n)

·空间复杂度:O(n)

总结：这题和爬楼梯也是类似，只是多了一个需要花费的部分，所以并没有什么难理解的地方