【动态规划】动态规划一

动态规划一

1.第 N 个泰波那契数
2.面试题 08.01. 三步问题
3.使用最小花费爬楼梯
4.解码方法

在这里插入图片描述

点赞👍👍收藏🌟🌟关注💖💖
你的支持是对我最大的鼓励，我们一起努力吧!😃😃

1.第 N 个泰波那契数

题目链接：1137. 第 N 个泰波那契数

题目分析：

在这里插入图片描述

返回第n个泰波那契数 Tn 的值。
n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2，这个公式可以转化一下看的更明白：
Tn = Tn-3 + Tn-2 + Tn-1， Tn等于前面三个数之和。T0，T1，T2已经给我们了。

在这里插入图片描述
接下来用动态规划的思想来解决这个问题。

算法原理：

动态规划思想有5步：

先确实状态表示
根据状态表示推导状态转移方程
初始化
填表顺序
返回值

动态规划做题流程一般是 先定义一个dp表，这个表可能是一维数组也可能是二维数组。然后想办法把这个dp表填满，里面某个位置的值就是我们的最终结果！

下面具体解释5步：

1.状态表示

是什么？dp表中某个位置的值代表什么含义

怎么来的？

题目要求
经验+题目要求
分析问题的过程中，发现重复子问题

比如这道题就可以根据题目要求来得到状态表示。你要返回第n个泰波那契数，那我让dp[0]表示第个泰波那契数，dp[1]表示第个泰波那契数，那最后返回dp[n]就行了。
dp[i]表示：第 i 个泰波那契数

在这里插入图片描述

2.状态转移方程

dp[i] 等于什么这个推导公式就是状态转移方程。
我们要想办法让之前的状态或者之后的状态来表示dp[i]。

这个题就已经告诉我们状态转移方程了，Tn就等于前三个泰波那契数和。dp[i]依赖前三个，并且是它们的和。dp[i] = dp[i-1] + dp[i-2] + dp[i-3]。

dp[i] 等于什么这个推导公式只能就题论题了！

在这里插入图片描述

3.初始化

保证填表的时候不越界

我们做动态规划就是为了把dp表填满，填表的时候不越界的意思是，我们要先知道怎么填表，就是根据状态转移方程填表。

就比如这道题我想填dp[4]，我仅需要知道前三个位置的值就可以填dp[4]了。

那为什么要保证不越界呢？
比如这个0、1、2这个位置，如果用状态转移方程来填这些位置的时候，比如0带进去出现-1、-2、-3，这个数组不能访问这些位置越界了！

因此用状态转移方程填表的时候必须要保证不越界的！

比如这道题前三个位置越界，我仅需要把前三个位置初始化。这道题也告诉我们了。

在这里插入图片描述

4. 填表顺序

为了填写当前状态的时候，所需要的状态已经计算过了。

比如初始化完dp[0]，dp[1]，dp[2]，直接去填dp[4]，需要知道前三个位置的值，但是现在并不知道dp[3]位置的值是多少。因此填表的时候必须要规定一个顺序。这道题就是从左往右填。

在这里插入图片描述

5.返回值

结合题目要求+状态表示

这道题让返回第n个泰波那契数，我们的状态表示第i个泰波那契数。因此直接返回dp[n]就行了。

在这里插入图片描述

只要完成这五步，动态规划算法原理就结束了。

动态规划编写代码就固定四步：

创建dp表
初始化
填表
返回值

class Solution {
public:int tribonacci(int n) {// 1.创建dp表// 2.初始化// 3.填表// 4.返回值// 处理一些边界情况if(n == 0) return 0;if(n == 1 || n == 2) return 1;vector<int> dp(n)dp[0] = 0, dp[1] = dp[2] = 1;for(int i = 3; i <= n; ++i){dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];}return dp[n];
};

简单分析一下时间复杂度O(N)，空间复杂度O(N)。

接下来学习一下空间优化的技巧。

动态规划的空间优化一般都是用滚动数组方式来优化的。

比如说这道题，我求dp[3] 需要 dp[0]、dp[1]、dp[2]三个位置，dp[4] 需要 dp[1]、dp[2]、dp[3]三个位置等等。

在这里插入图片描述

有没有发现当我们在求某一个位置的值时仅需要知道前面三个状态的值就可以了。比如dp[4]用不到dp[0]，dp[5]用不到dp[0]、dp[1]，那求其他位置的时候这些用不到的位置就浪费空间了。

在这里插入图片描述

当我们再填dp表的时候，求dp[i]的时候，前面一些状态就可以丢去，仅需要它前面若干个状态就可以了，像这样一种情况都可以用滚动数组来做优化！

优化后O(N^2)->O(N)，O(N)->O(1)。

如何优化？
仅需要几个变量就可以了。

比如这道题求某个位置的值需要知道前面三个位置状态的值，因此需要a、b、c、d四个变量就行了。a、b、c记录前三个位置状态值，d记录当前求得位置得状态值。初始的时候a = 0 ，b = 1， c = 1 ，d在dp[3]。比如算完dp[3]，然后让a、b、c、d滚动一下，算dp[4] 。像这样的技巧就是滚动数组。

在这里插入图片描述

这里有个细节问题。滚动就是要完成赋值操作。相当于b的值给a，c的值给b，d的值给c。现在有两种赋值操作，从前向后赋值还是从后像前赋值？

第一种方式是对的，因为第二种方式赋值完都是a、b、c都是d！

在这里插入图片描述

class Solution {
public:int tribonacci(int n) {// 1.创建dp表// 2.初始化// 3.填表// 4.返回值// 处理一些边界情况if(n == 0) return 0;if(n == 1 || n == 2) return 1;// vector<int> dp(n)// dp[0] = 0, dp[1] = dp[2] = 1;// for(int i = 3; i <= n; ++i)// {//     dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];// }// return dp[n];//空间优化int a = 0, b = 1, c = 1, d = 0;for(int i = 3; i <= n; ++i){d = a + b + c;a = b; b = c; c = d;}return d;}
};

2.面试题 08.01. 三步问题

题目链接： 面试题 08.01. 三步问题

题目分析：

在这里插入图片描述
楼梯有n阶台阶，小孩一次可以上1阶、2阶或3阶。

从这就可以看出来到达4需要4前面三个位置位置到达方法相加，同理后面也是这样。
在这里插入图片描述

算法原理：

动态规划：

1.状态表示

根据经验+题目要求
经验就是以某个位置为结尾研究问题，或者是以某个位置为起点研究问题，研究的问题根据题目要求而来。

我们常用的是以某个位置为结尾研究问题。

假设位置是i，以i位置为结尾结合这道题要求到达第i个台阶有多少种方法。状态表示就有了。

dp[i]表示：到达i位置时，一共有多少种方法。

2.状态转移方程

也是根据经验来的：以i位置的状态，最近的一步，来划分问题

比如这道题，到达i位置最近的一步，要么是 i-1 走一步，要么是 i-2 走两步，要么是 i-3 走三步这些所有情况。 以i位置的状态，最近的一步，划分出三种情况。接下来看着三种情况能不能用之前的状态表示一下。

从i-3到达i一共有有多少种方法，从i-3到i是不是先要到达i-3，假设到i-3有x种方法，然后在每一种方法后面加上到i这一步就可以了。x->i，这个x表示达到i-3有多少种方法，x正好是dp[i-3]。同理i-2，i-1都是。
在这里插入图片描述

3.初始化

填表的时候不越界

在这里插入图片描述

4.填表顺序

从左到右

5.返回值

结合题目要求，返回到达第n层有多少种方法，dp[n]。

class Solution {
public:int waysToStep(int n) {// 1.创建dp表// 2.初始化// 3.填表// 4.返回值const int MOD = 1e9+7;//边界问题if(n == 1 || n == 2) return n;if(n == 3) return 4;vector<int> dp(n+1);dp[1] = 1, dp[2] = 2, dp[3] = 4;for(int i = 4; i <= n; ++i)dp[i] = (((dp[i - 1] + dp[i - 2]) % MOD ) + dp[i - 3]) % MOD;return dp[n];}
};

3.使用最小花费爬楼梯

题目链接：746. 使用最小花费爬楼梯

题目分析：

在这里插入图片描述

本题求达到楼梯顶部的最低花费。向上爬楼梯需要支付本层的费用，然后可以爬一层或者两层。可以从下标为 0 或下标为 1 的台阶开始爬楼梯。

注意要求的是爬到楼顶的最低花费，即使到达数组最后一个还需要在往上爬一步加上本层的费用。
在这里插入图片描述

算法原理：

动态规划解法一：

1.状态表示

经验+题目要求

向这种一维数组的dp一般经验分为两种：

以某个位置为结尾，巴拉巴拉(根据题目要求把它替换掉)
以某个位置为起点，巴拉巴拉

解法一用的是第一种以某个位置为结尾，巴拉巴拉，接下来看如何替换掉巴拉巴拉。这道题让找达到楼梯顶部的最低花费。那如果以 i 位置结尾，求的是最少花费。那我就可以得到这样一个状态表示，dp[i]表示，到达 i 位置时，最少花费

在这里插入图片描述

2.状态转移方程

分析状态转移方程的一条总线:
用 i 位置之前或者之后的状态，推导 dp[i] 的值
如i之前状态 dp[i-2]、dp[i-1]，i之后状态 dp[i+1]，dp[i+2]

如何推导出dp[i]的值呢？
根据最近的一步，来划分问题

如这道题，先到达i-1的位置，从i-1位置花费i-1位置的费用走一步到i，或者可以先到达i-2的位置，花费i-2位置的费用走两步到i。这是依据 i 位置最近的一步来划分出的两种情况。因为要求花费最少，所有两种情况种选择最少的。接下来看这两种情况能不能用之前的状态表示一下。

cost[i-1]是定值无法改变，先到达i-1位置也是有一个花费，如果想求i位置最小花费，是不是要先找到i-1位置的最小花费，只要找到i-1位置的最小花费在加上cost[i-1]走一步，就是第一种情况的最小花费。到达i-1位置最小花费不就是dp[i-1] 表示到达i-1位置，最小花费。同理i-2也是这样分析的。然后求的是两种情况的最小值。因此状态转移方程就有了。

在这里插入图片描述

3.初始化

在这里插入图片描述

4.填表顺序

由前面两个位置填后面的位置。。。
从左往右

在这里插入图片描述

5.返回值

结合题目要求，返回到达楼梯最小花费。dp表数组下标为n的地方。所以返回 dp[n]

在这里插入图片描述

class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {// 1.创建dp表// 2.初始化// 3.填表// 4.返回// 解法一int n = cost.size();vector<int> dp(n+1);//dp[0] = dp[1] = 0;for(int i = 2; i <= n; ++i)dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]);return dp[n];   }
};

动态规划解法二：

其实第二种解决就是换了一种状态表示。

1.状态表示

经验+题目要求
以 i 位置为起点，巴拉巴拉

以i位置为起点，然后要去楼顶还要是最小花费，因此 dp[i]表示，从i位置出发，到达楼顶，此时最小花费。

在这里插入图片描述

2.状态转移方程

分析状态转移方程的一条总线:
用 i 位置之前或者之后的状态，推导 dp[i] 的值
如i之前状态 dp[i-2]、dp[i-1]，i之后状态 dp[i+1]，dp[i+2]

如何推导出dp[i]的值呢？
根据最近的一步，来划分问题

i位置表示到达楼梯的最小花费，它最近一步是不是支付完i位置的费用，往后走一步到i-1的位置，然后从i-1位置出发到楼顶。或者是往后走两步到i-2的位置。然后从i-2位置出发到楼顶。接下来看这两种情况能不能用之前的状态表示一下。

支付cost[i]是固定的，我想让第一种情况最小我得让i+1位置最小，我得知道从i+1位置出发到i位置最小花费。dp[i+1]表示从i+1位置出发，到达楼顶，此时最小花费，然后加上cost[i] 就是第一种情况最小花费。同理dp[i+2]表示从i+1位置出发，到达楼顶，此时最小花费加上cost[i] 就是第二种情况最小花费。然后在取这两种情况中最小花费。

在这里插入图片描述

3.初始化

因为我们是从某一个位置到楼顶，所以dp数组不需要额外在开一个位置。直接跟原始数组一样大就可以了。

其次我们需要先知道i+1的位置和i+2的位置才能知道dp[i]的值，因此先把最后两个位置初始化

在这里插入图片描述

4.填表顺序

知道后面两个位置的值，就可以得到前面的值，因此从右往左
在这里插入图片描述

5.返回值

我们最开始要么是从0开始，要是是从1开始。所以返回的是dp[0]，dp[1]中的最小值。

在这里插入图片描述

class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {// 1.创建dp表// 2.初始化// 3.填表// 4.返回// 解法一// int n = cost.size();// vector<int> dp(n+1);// //dp[0] = dp[1] = 0;// for(int i = 2; i <= n; ++i)//     dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]);// return dp[n];   // 解法二int n = cost.size();vector<int> dp(n);dp[n - 1] = cost[n - 1], dp[n - 2] = cost[n - 2];for(int i = n - 3; i >= 0; --i)dp[i] = min(dp[i + 1] + cost[i], dp[i + 2] + cost[i]);return min(dp[0], dp[1]);}
};

4.解码方法

题目链接：91. 解码方法

题目分析：

在这里插入图片描述

A-Z --> 1-26，将一个经过编码的只包含数字的字符串解码看有多少种解码方式。

注意这样的情况 “06”，不仅不能每个单独编码，也不能合在一起进行编码。
‘0’ 不在 ‘1-9’ 范围内，‘06’ 不在 ‘10-26’ 范围内。同样"60"也不单独编码和合在一起编码。

在这里插入图片描述
算法原理：

1.状态表示

经验+题目要求
以 i 位置为结尾，巴拉巴拉。
接下来根据题目要求替换巴拉巴拉。
题目要求求s字符串有多少种解码方法。是不是就从从开始到结尾的解码总数。那dp[i]就可以这样表示。
dp[i]表示，以 i 位置为结尾时，解码方法的总数。

在这里插入图片描述

2.状态转移方程

根据i状态最近的一步，来划分问题
最近一步就是解码到i位置的时候，解码到i位置有两种情况，i位置单独解码，i-1和i位置合在一起解码。因为是以i位置为结尾的，所有i+1位置还没有到，暂时不考虑。

但是解码并不是你想解码就解码，必须要符合条件，否则不能解码。所有单独解码和合在一起解码都有成功或者失败的可能。

s[i] 单独解码
解码成功 s[i] 必须在 ‘1’ - ‘9’ 范围内，解码成功要的是总数，i位置解码成功，是不是前面 0到i-1位置解码成功的所有情况后面在添加一个 i 位置的字符就行了。而 0到i-1位置解码成功的所有情况 dp[i-1] 不就是吗。

解码失败 s[i] 不在 ‘1’ - ‘9’ 范围内，那以 i 位置为结尾就没有解码方案数了，就如"60"这种情况。前面不管有多少种解码方案那s[i]失败，那整个就没有解码方案。我们要的是整体的解码方案。

s[i-1] 和 s[i] 合一起解码
解码成功 把s[i-1] 和 s[i] 放在一起解码成功，条件是10 <= b*10+a <= 26，为什么不是1-26呢？因为 01到09没有这种情况，所以只能是10到26。解码成功方案数合上面类似 0到i-2所有解码方案后面添加上s[i-1]合s[i]在一起的解码就行了。dp[i-2]。

解码失败 同理最后一个位置解码失败，不管前面怎么样，整体解码方案就是0

在这里插入图片描述

3.初始化

因为会用到i-1和i-2所以要对0和1初始化。
在这里插入图片描述

4.填表顺序

填dp[i]要知道dp[i-1]和dp[i-2]的位置，所以从左到右

5.返回值

dp[i]表示以 i 位置为结尾时，解码方法的总数，题目要求求整个字符串所有解码方案，所以返回的是dp[n-1]。

class Solution {
public:int numDecodings(string s) {// 1.创建dp表// 2.初始化// 3.填表// 4.返回值int n = s.size();vector<int> dp(n);dp[0] = s[0] != '0';//处理边界情况if(n == 1) return dp[0];if(s[0] != '0' && s[1] != '0')dp[1] += 1;int tmp = (s[0] - '0') * 10 + s[1] - '0'; //前两个位置表示的数if(tmp >= 10 && tmp <= 26)dp[1] += 1;for(int i = 2; i < n; ++i){if(s[i] != '0') dp[i] += dp[i - 1];//处理单独编码的情况int tmp = (s[i - 1] - '0') * 10 + s[i] - '0';//处理合在一起编码的情况if(tmp >= 10 && tmp <= 26)dp[i] += dp[i - 2];} return dp[n-1];}
};

之前写的dp代码都比较短，但是这里的dp初始化为什么这么长并且，部分初始化代码和填表中代码类似，有没有可能写在一起？使代码编码简洁，是有的。

细节问题：

做dp问题的时候，会经常处理比较繁琐的边界情况以及初始化。为了能更好的处理这些情况，对于一维数组我们可以把整个数组统一往后移动一位，也就是数组多开一个位置的技巧。

处理边界问题以及初始化问题的技巧
数组多开一个位置

之前旧dp表中的位置的值要在新的dp表中对应位置往后放一个。
在这里插入图片描述
多出来的位置我们称为虚拟位置。多出来这个位置的作用，前面在旧的dp表要初始化0和1位置，在新dp表中虽然也初始化0和1的位置，但是确是方便了不少。

之前旧dp表初始化1的位置非常麻烦。现在旧表中1的位置跑到新dp表中1填表的下标里面了。我在新dp表中填表中就把旧dp表中1的位置干掉了。这样就非常爽了。
在这里插入图片描述

但是却有两个注意事项：

虚拟节点里面的值，要保证后面填表是正确的
下标的映射关系

虚拟节点里面的值，要保证后面填表是正确的

比如新dp表中，填表时的 dp[2] = dp[1] + dp[0]，dp[1]是不会错误的因为它的初始化是和旧dp[0]是一样的。但是dp[0]是我们构建出来的，它里面值存放多少是不是就会影响到dp[2]的值。

一般情况下，这个虚拟节点的值存的是 0 ，但是这道题就不一样了，dp[0]里面存0是不正确的。求dp[2]如果用到dp[0]，是不是就是1和2的位置合在一起能解码成功，然后我才加上dp[0]，如果dp[0]是0那不就是少加了一种情况吗。因此这个dp[0]填1。

在这里插入图片描述

总体来说就是具体问题具体分析！看虚拟节点的值到底填几。

下标的映射关系

在新dp表中，初始化dp[1]的时候，看的是s[0]这个位置能否解码成功，对应就是s[1-1] != ‘0’。因为我们多加个一个位置，下标统一往后移动一位，如果还想和之前一样找之前位置这里 s[i] 就必须多加一个 -1 的操操作。

class Solution {
public:int numDecodings(string s) {// 1.创建dp表// 2.初始化// 3.填表// 4.返回值//优化后int n = s.size();vector<int> dp(n+1);dp[0] = 1; // 保证后面填表是正确的 dp[1] = s[1-1] != '0';for(int i = 2; i <= n; ++i){if(s[i - 1] != '0') dp[i] += dp[i - 1];//处理单独编码的情况int tmp = (s[i - 2] - '0') * 10 + s[i - 1] - '0';//处理合在一起编码的情况if(tmp >= 10 && tmp <= 26)dp[i] += dp[i - 2];}return dp[n];}
};