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

这篇具有很好参考价值的文章主要介绍了C++动态规划-线性dp算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

莫愁千里路

自有到来风

C++动态规划-线性dp算法,C++,c++,动态规划,开发语言,算法,c语言


CSDN 请求进入专栏                                    X

是否进入《C++专栏》?

确定

目录

 线性dp简介

斐波那契数列模型 

第N个泰波那契数

思路:

代码测试:

 三步问题

思路:

代码测试:

最小花费爬楼梯

思路:

代码测试:

 路径问题

数字三角形

思路:

代码测试:

不同路径 

思路:

代码测试:

LIS模型

最长递增子序列

思路:

代码测试:

 线性dp简介

线性DP(Introduction)

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

C++动态规划-线性dp算法,C++,c++,动态规划,开发语言,算法,c语言

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

思路:

C++动态规划-线性dp算法,C++,c++,动态规划,开发语言,算法,c语言

<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]之间

思路:

C++动态规划-线性dp算法,C++,c++,动态规划,开发语言,算法,c语言

C++动态规划-线性dp算法,C++,c++,动态规划,开发语言,算法,c语言

C++动态规划-线性dp算法,C++,c++,动态规划,开发语言,算法,c语言

C++动态规划-线性dp算法,C++,c++,动态规划,开发语言,算法,c语言

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

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

C++动态规划-线性dp算法,C++,c++,动态规划,开发语言,算法,c语言

<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

思路:

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

C++动态规划-线性dp算法,C++,c++,动态规划,开发语言,算法,c语言

C++动态规划-线性dp算法,C++,c++,动态规划,开发语言,算法,c语言

<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]

C++动态规划-线性dp算法,C++,c++,动态规划,开发语言,算法,c语言

代码测试:

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];   
    }
};

 路径问题

数字三角形

题目链接:数字三角形


题目描述#

观察下面的数字金字塔

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

C++动态规划-线性dp算法,C++,c++,动态规划,开发语言,算法,c语言

在上面的样例中,从 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

思路:

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

C++动态规划-线性dp算法,C++,c++,动态规划,开发语言,算法,c语言

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

贪心只注重眼前的利益(如上图),贪心策略算出的数字的和是:28 不符合我们的最大值

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

注意:

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

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

例如:

C++动态规划-线性dp算法,C++,c++,动态规划,开发语言,算法,c语言

C++动态规划-线性dp算法,C++,c++,动态规划,开发语言,算法,c语言

我们找到倒数第二排的元素 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

C++动态规划-线性dp算法,C++,c++,动态规划,开发语言,算法,c语言

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

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

C++动态规划-线性dp算法,C++,c++,动态规划,开发语言,算法,c语言

<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:

C++动态规划-线性dp算法,C++,c++,动态规划,开发语言,算法,c语言

输入: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

状态转移方程的得出

C++动态规划-线性dp算法,C++,c++,动态规划,开发语言,算法,c语言

初始化问题

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

C++动态规划-线性dp算法,C++,c++,动态规划,开发语言,算法,c语言

注意:

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

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

C++动态规划-线性dp算法,C++,c++,动态规划,开发语言,算法,c语言

我们只要将 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

思路:

子序列的介绍:

C++动态规划-线性dp算法,C++,c++,动态规划,开发语言,算法,c语言

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

状态转移方程的推理:

C++动态规划-线性dp算法,C++,c++,动态规划,开发语言,算法,c语言

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

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

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

<1>状态表示 dp[i]表示以 i 位置为结尾的所有子序列中,最长递增子序列的长度
<2>状态转移方程

dp[i] = max(dp[i]+1,dp[i])文章来源地址https://www.toymoban.com/news/detail-825899.html

<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;
    }
};

到了这里,关于C++动态规划-线性dp算法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • AcWing算法学习笔记:动态规划(背包 + 线性dp + 区间dp + 计数dp + 状态压缩dp + 树形dp + 记忆化搜索)

    算法 复杂度 时间复杂度0(nm) 空间复杂度0(nv) 代码 算法 通过滚动数组对01背包朴素版进行空间上的优化 f[i] 与 f[i - 1]轮流交替 若体积从小到大进行遍历,当更新f[i, j]时,f[i - 1, j - vi] 已经在更新f[i, j - vi]时被更新了 因此体积需要从大到小进行遍历,当更新f[i, j]时,f[i - 1,

    2024年02月21日
    浏览(43)
  • c++ 算法之动态规划—— dp 详解

    dp 是 c++ 之中一个简单而重要的算法,每一个 OIer 必备的基础算法,你知道它究竟是什么吗? 目录 一、简介         1.为什么不能贪心?         2.揭秘 dp   二、应用         1.定义         2.边界值         3.动态转移方程         4.结果         5.代码

    2024年04月09日
    浏览(47)
  • C++算法 —— 动态规划(7)两个数组的dp

    每一种算法都最好看完第一篇再去找要看的博客,因为这样会帮你梳理好思路,看接下来的博客也就更轻松了。当然,我也会尽量在写每一篇时都可以不懂这个算法的人也能边看边理解。 动规的思路有五个步骤,且最好画图来理解细节,不要怕麻烦。当你开始画图,仔细阅读

    2024年02月07日
    浏览(54)
  • C++ DP算法,动态规划——背包问题(背包九讲)

    有N件物品和一个容量为 V V V 的背包。放入第i件物品耗费的空间是 C i C_i C i ​ ,得到的价值是 W i W_i W i ​ 。 求解将哪些物品装入背包可使价值总和最大。 这是最基础的背包问题,特点是:每种物品仅有一件,可以选择放或不放。 用子问题定义状态:即 F [ i , v ] F[i, v] F

    2024年02月16日
    浏览(51)
  • 【数位dp】【动态规划】C++算法:233.数字 1 的个数

    视频算法专题 动态规划汇总 给定一个整数 n,计算所有小于等于 n 的非负整数中数字 1 出现的个数。 示例 1: 输入:n = 13 输出:6 示例 2: 输入:n = 0 输出:0 提示: 0 = n = 10 9 本题比较简单,主要讲封装类。m_vPre记录上一位所有状态,程序结束时,记录的是最后一位的所有

    2024年01月16日
    浏览(42)
  • 动态规划(DP)入门——线性DP

    在了解线性DP之前,我们首先要知道什么是动态规划,即为将一种复杂问题,分解成很多重叠的子问题,并通过子问题的解得到整个问题的解的算法。听起来比较抽象,动态规划简单来说就是确定问题的状态,通常题目都会提示,一般为“到第i个为止,xx为j(xx为k)的方案数/最

    2024年02月19日
    浏览(48)
  • 动态规划——线性DP

    暴力搜索:由可行的所有起点出发,搜索出所有的路径。 但是深搜的算法时间复杂度要达到 O ( 2 n ) O(2^n) O ( 2 n ) (每个数都有选或不选的两个选择),指数级的时间复杂度在本题中( n ≤ 100 n≤100 n ≤ 100 )显然是不能接受的。那么再观察这个这棵递归树,可以发现其中有很

    2024年01月19日
    浏览(48)
  • 动态规划:线性DP

    2024年02月06日
    浏览(40)
  • 「算法小记」-2:矩阵链相乘的方案数【迭代/递归/动态规划/区域化DP/记忆化搜索】(C++ )

    😎 作者介绍:我是程序员洲洲,一个热爱写作的非著名程序员。CSDN全栈优质领域创作者、华为云博客社区云享专家、阿里云博客社区专家博主、前后端开发、人工智能研究生。公粽号:程序员洲洲。 🎈 本文专栏:本文收录于洲洲的《算法小记》系列专栏,该专栏记录了许

    2024年02月05日
    浏览(54)
  • [动态规划]——线性DP(LIS/LCS/LCIS等) 详解

    线性DP,是较常见的一类动态规划问题,其是在线性结构上进行状态转移,这类问题不像背包问题、区间DP等有固定的模板 线性动态规划的目标函数为特定变量的线性函数,约束是这些变量的线性不等式或等式,目的是求目标函数的最大值或最小值 因此,除了少量问题(如:

    2024年02月10日
    浏览(45)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包