C++动态规划-线性dp算法

莫愁千里路

自有到来风

---

CSDN 请求进入专栏                                    X 是否进入《C++专栏》? 确定

---

目录

 线性dp简介

斐波那契数列模型 

第N个泰波那契数

思路：

代码测试：

 三步问题

思路：

代码测试：

最小花费爬楼梯

思路：

代码测试：

 路径问题

数字三角形

思路：

代码测试：

不同路径 

思路：

代码测试：

LIS模型

最长递增子序列

思路：

代码测试：

 线性dp简介

线性DP(Introduction)

线性DP是动态规划问题中的一类问题，指状态之间有 线性关系 的动态规划问题

DP解题套路
<1>根据题意列出状态表示

dp表里面的值所代表的含义

分析问题的过程中发现重复子问题
<2>根据状态表示列出状态转移方程

dp[i]等于什么
<3>初始化

填dp表的时候不能越界访问
<4>填表顺序

递推求解的顺序

斐波那契数列模型 

第N个泰波那契数

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

---

泰波那契序列 Tn 定义如下： 

T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2

给你整数 n，请返回第 n 个泰波那契数 Tn 的值。

示例 1：

输入：n = 4
输出：4
解释：
T_3 = 0 + 1 + 1 = 2
T_4 = 1 + 1 + 2 = 4

示例 2：

输入：n = 25
输出：1389537

提示：

• 0 <= n <= 37
• 答案保证是一个 32 位整数，即 answer <= 2^31 - 1

---

思路：

<1>状态表示	dp[i]表示第 i 个泰波那契数的值
<2>状态转移方程	dp[i] = dp[i-1] + dp[i-2] + dp[i-3]  (Tn+3 = Tn + Tn+1 + Tn+2)
<3>初始化	dp[0] = 0，dp[1] = dp[2] = 1
<4>填表顺序	从左至右

---

代码测试：

时间复杂度O(N)

空间复杂度O(N)

class Solution 
{
public:int tribonacci(int n) {//防止数组越界if(n == 0) return 0;if(n == 1||n == 2) return 1;vector<int> dp(n+1);//初始化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];}
};

 三步问题

题目链接：三步问题

---

三步问题。有个小孩正在上楼梯，楼梯有n阶台阶，小孩一次可以上1阶、2阶或3阶。实现一种方法，计算小孩有多少种上楼梯的方式。结果可能很大，你需要对结果模1000000007。

示例1:

 输入：n = 3 
 输出：4
 说明: 有四种走法

示例2:

 输入：n = 5
 输出：13

提示:

1. n范围在[1, 1000000]之间

---

思路：

我们发现从 4 层开始就是前三项之和，第五层就是：7 + 4 + 2= 13

所以从第四层开始，满足斐波那契规律

<1>状态表示	以 i 为结尾，dp[i]表示到达 i 位置时，一共有多少种方法
<2>状态转移方程	以 i 的位置的状态，最近的一步开始划分问题 从(i-1)到 i：dp[i-1] 从(i-2)到 i：dp[i-2] 从(i-3)到 i：dp[i-3] dp[i] = dp[i-1]+dp[i-2]+dp[i-3]
<3>初始化	dp[1] = 1，dp[2] = 2，dp[3] = 4
<4>填表顺序	从左往右

代码测试：

时间复杂度O(N)

空间复杂度O(N)

class Solution 
{
public:int waysToStep(int n) {//取模数据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];}
};

最小花费爬楼梯

题目链接：最小花费爬楼梯

---

数组的每个下标作为一个阶梯，第 i 个阶梯对应着一个非负数的体力花费值 cost[i]（下标从 0 开始）。

每当爬上一个阶梯都要花费对应的体力值，一旦支付了相应的体力值，就可以选择向上爬一个阶梯或者爬两个阶梯。

请找出达到楼层顶部的最低花费。在开始时，你可以选择从下标为 0 或 1 的元素作为初始阶梯。

示例 1：

输入：cost = [10, 15, 20]
输出：15
解释：最低花费是从 cost[1] 开始，然后走两步即可到阶梯顶，一共花费 15 。

 示例 2： 

输入：cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
输出：6
解释：最低花费方式是从 cost[0] 开始，逐个经过那些 1 ，跳过 cost[3] ，一共花费 6 。

提示：

• 2 <= cost.length <= 1000
• 0 <= cost[i] <= 999

---

思路：

由题意可知：我们的楼层顶部并不是数组的末元素，而是末元素的下一位

​

<1>状态表示	以 i 为结尾，dp[i]表示到达 i 位置时，最小花费
<2>状态转移方程	使用之前或者之后的状态，推导出dp[i]的值 根据最近的一步来划分问题 (1)先到达 i-1 的位置，然后支付cost[i-1]，走一步：dp[i-1]+cost[i-1] (2)先到达 i-2 的位置，然后支付cost[i-2]，走二步：dp[i-2]+cost[i-2] dp[i] = min(dp[i-1]+cost[i-1]，dp[i-2]+cost[i-2])
<3>初始化	由题意 你可以选择从下标为 0 或 1 的元素作为初始阶梯 得： dp[0] = dp[1] = 0
<4>填表顺序	从左往右
<5>返回值	dp[n]

代码测试：

class Solution 
{
public:int minCostClimbingStairs(vector<int>& cost) {//计算数组长度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];   }
};

 路径问题

数字三角形

题目链接：数字三角形

---

题目描述#

观察下面的数字金字塔

写一个程序来查找从最高点到底部任意处结束的路径，使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。

在上面的样例中，从 7→3→8→7→5 的路径产生了最大权值。

输入格式#

第一个行一个正整数 r 表示行的数目。

后面每行为这个数字金字塔特定行包含的整数。

输出格式#

单独的一行,包含那个可能得到的最大的和。

输入输出样例#

输入 #1

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5 

输出 #1

30

---

思路：

在看到数字三角形的构造时，我们首先想到用 二维数组 来存放整个三角形（行与列）

也许有人会想到 贪心算法 来实现，但是贪心算法在这里是不适用的

贪心只注重眼前的利益（如上图），贪心策略算出的数字的和是：28 不符合我们的最大值

所以眼光放长，我们要的是最后的数字和最大，尝试用 动态规划 解决问题

注意：

我们发现从上面往下一步步走很麻烦，直接搜索肯定超时

所以我们的切入点是 由下至上 的回溯，依层次更换改动大值，回到顶端时，就是结果

例如：

我们找到倒数第二排的元素 2 ，此时只有两种方法可以走，左下方或者右下方

我们要保证数字和最大，所以必然选择 右下方 ，这个时候的较大值为 7

同理：我们考虑倒数第二排的元素 7 ，较大值为 12

依次类推则倒数第二排变为：

7 12 10 10 

因为我们的倒数第二排已经包含了最后一排的最优解，所以我们的三角形可以简化成：

        7 3   8 8   1   0 7   12  10  10 

方法同上我们找到倒数第二排的元素 8 ，再比较走两条路的值，右边的值更大，选择右边的值，所以这个时候的较大值为 20

以此类推，得到下面的数字三角形：

        7 3   8 20  13  10 

           7 23   21

          30 23   21 20   13   10 7   12   10  10 
4    5    2    6    5 

最后得到我们的最大数字之和为 30

所以我们的最佳路径是：7→3→8→7→5

思路我们已经理清了，接下来开始推导我们的状态转移方程：

<1>状态表示	以 [i，j] 为结尾，dp[ i ][ j ]表示到达 [i，j] 位置时，最大的数字之和
<2>状态转移方程	dp[i][j]+=max(dp[i+1][j]，dp[i+1][j+1])
<3>初始化	按要求输入
<4>填表顺序	从下至上，从左至右
<5>返回值	dp[1][1]
<6>小总结	画图求解，发现规律，列出状态转移方程

代码测试：

#include<bits/stdc++.h>
using namespace std;
int main()
{int n = 0;cin>>n;vector<vector<int>> dp((n+1),vector<int>(n+1));//初始化for(int i = 1;i<=n;i++)for(int j = 1;j<=i;j++)cin>>dp[i][j];//顺序填表for(int i = n-1;i>=1;i--)for(int j = 1;j<=i;j++)//状态转移方程dp[i][j]+=max(dp[i+1][j],dp[i+1][j+1]);//返回值cout<<dp[1][1]<<endl;return 0;
}

不同路径 

 题目链接：不同的路径

---

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角

（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

示例 1：

输入：m = 3, n = 7
输出：28

示例 2：

输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下

示例 3：

输入：m = 7, n = 3
输出：28

示例 4：

输入：m = 3, n = 3
输出：6

提示：

• 1 <= m, n <= 100
• 题目数据保证答案小于等于 2 * 10^9

---

思路：

二维dp

状态转移方程的得出

初始化问题

为了防止数组越界，所以我们要考虑 dp 的初始化问题

注意：

<1>然后在考虑虚拟位置的值，要保证我们后面填表的结果是正确的

<2>二维数组的行和列都要加一（加上了虚拟位置）

我们只要将 dp[0][1] 或者 dp[0][1] 的位置初始化为 1 就可以了 

<1>状态表示	以[i，j]为结尾时，dp[i][j]表示走到[i，j]的位置，一共有多少种方式
<2>状态转移方程	dp[ i ][ j ] = dp[ i - 1 ][ j ] + dp[ i ][ j - 1]
<3>初始化	dp[0][1] = 1
<4>填表顺序	从左至右，从上至下
<5>返回值	dp[m][n]

代码测试：

class Solution 
{
public:int uniquePaths(int m, int n) {vector<vector<int>> dp(m+1,vector<int>(n+1));//初始化dp[0][1] = 1;//顺序填表for(int i = 1;i<=m;i++)for(int j = 1;j<=n;j++)//状态转移方程dp[i][j] = dp[i-1][j]+ dp[i][j-1];//返回值return dp[m][n];}
};

LIS模型

最长递增子序列

题目链接：最长递增子序列

---

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

 

示例 1：

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

示例 2：

输入：nums = [0,1,0,3,2,3]
输出：4

示例 3：

输入：nums = [7,7,7,7,7,7,7]
输出：1

---

思路：

子序列的介绍：

子序列指的是一个序列中，按照原顺序选出若干个 一定连续 的元素所组成的序列

状态转移方程的推理：

初始化：将dp标准的状态成最坏的情况，最后更新dp表就可以了

填表顺序：因为我们要填 dp[i] 就要用到前面的值，所以是：从左往右

注意：要判断 nums[j]<nums[i]

<1>状态表示	dp[i]表示以 i 位置为结尾的所有子序列中，最长递增子序列的长度
<2>状态转移方程	dp[i] = max(dp[i]+1,dp[i])
<3>初始化	dp表中所有元素都置为1
<4>填表顺序	从左往右
<5>返回值	dp表中的最大值

代码测试：

class Solution 
{
public:int lengthOfLIS(vector<int>& nums) {int n = nums.size();//初始化vector<int> dp(n,1);int ret = 1;//顺序填表for(int i = 1;i<n;i++){for(int j = 0;j<i;j++)//前提条件if(nums[j]<nums[i])//状态转移方程dp[i] = max(dp[j]+1,dp[i]);ret = max(ret,dp[i]);}//返回值return ret;}
};