【动态规划专栏】--基础-- 动态规划经典题型

article/2025/10/7 4:18:34

目录

动态规划

动态规划思维（基础）

状态表示（最重要）

状态转移方程（最难）

初始化（细节）

填表顺序（细节）

返回值（结果）

1、第 N 个泰波那契数⭐

【题目解析】

【算法原理】

C++ 算法代码

复杂度分析

【空间优化 - 滚动数组】

C++ 算法代码

复杂度分析

2、三步问题⭐

【题目解析】

【算法原理】

C++ 算法代码

复杂度分析

【空间优化 - 滚动数组】

C++ 算法代码

复杂度分析

3、使用最小花费爬楼梯⭐

【题目解析一】

【算法原理一】

C++ 算法代码

复杂度分析

【空间优化 - 滚动数组一】

C++ 算法代码

复杂度分析

【题目解析二】

【算法原理二】

C++ 算法代码

复杂度分析

【空间优化 - 滚动数组二】

C++ 算法代码

复杂度分析

总结

动态规划

动态规划思维（基础）

        动态规划一般会先定义一个dp表，dp表一般为一维数组 / 二位数组。如：一维数组，会先创建一个一维数组（dp表），接下来就是想办法将这个dp填满，而填满之后里面的某一个值就是最终结果。

状态表示（最重要）

#问：是什么？

  • 就是dp[i]所代表的含义。

#问：怎么来？

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

状态转移方程（最难）

#问：是什么？

  • dp[i] = ?。

初始化（细节）

#问：有什么作用？

  • 保证填表的时候不越界。

        dp表是根据状态转移方程进行的，而状态转移方程是通过已有状态推出未知状态。

填表顺序（细节）

#问：有什么作用？

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

返回值（结果）

        题目要求 + 状态表示。

1、第 N 个泰波那契数⭐

1137. 第 N 个泰波那契数 - 力扣（LeetCode）

​

【题目解析】

         泰波那契序列 Tn 是从 T0 开始的，也就是说Tn的个数是 n+1 需要注意。

​

【算法原理】

#：状态表示：

        这道题可以「根据题目的要求」直接定义出状态dp[i] 表示：第 i 个泰波那契数的值。

#： 状态转移方程：
         题目已经非常贴心的告诉我们了：dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3] 。
#： 初始化：

         从我们的递推公式可以看出， dp[i] 在 i = 0 以及 i = 1 的时候是没有办法进行推导的，因为 dp[-2] 或 dp[-1] 不是⼀个有效的数据。 因此我们需要在填表之前，将 0, 1, 2 位置的值初始化。题⽬中已经告诉我们 dp[0] = 0，dp[1] = dp[2] = 1 。

#：填表顺序：

         毫无疑问是「从左往右」。
#： 返回值：
        应该返回 dp[n] 的值。

C++ 算法代码

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

复杂度分析

  • 时间复杂度：O(n)。
  • 空间复杂度：O(n)。

【空间优化 - 滚动数组】

        通过上述图可以发现。

​

        dp[i]是只与前三个元素相关，所以我们可以将代码写为如下：

C++ 算法代码

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

复杂度分析

  • 时间复杂度：O(n)。
  • 空间复杂度：O(1)。

2、三步问题⭐

 面试题 08.01. 三步问题 - 力扣（LeetCode）

【题目解析】

         散步问题 dpn 是从 dp1 开始的，也就是说 Tn 的个数是 n + 1 需要注意，将 pd[0] 单独放在一旁有益于代码的书写。

        对应的阶梯是由前三个阶梯而来。

【算法原理】

#：状态表示：

        这道题可以根据 「经验 + 题目要求」 直接定义出状态 dp[i] 表示：到达 i 位置时，⼀共有多少种方法。
#： 状态转移方程：
        以 i 位置状态的最近的⼀步，来分情况讨论： 如果 dp[i] 表示小孩上第 i 阶楼梯的所有方式，那么它应该等于所有上⼀步的方式之和：
  1. 上⼀步上⼀级台阶， dp[i] += dp[i - 1] ；
  2. 上⼀步上两级台阶， dp[i] += dp[i - 2] ；
  3. 上⼀步上三级台阶， dp[i] += dp[i - 3] ；
        即上述，dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3] 。 需要注意的是，由于结果可能很大，需要对结果取模。 在计算的时候，三个值全部加起来再取模，即 (dp[i - 1] + dp[i - 2] + dp[i - 3]) % 1000000007 是不可取的，对于这类需要取模的问题，我们每计算⼀次，都需要取⼀次模。
#： 初始化：
        从我们的递推公式可以看出， dp[i] 在 i = 0, i = 1 以及 i = 2 的时候是没有办法进行推导的，因为 dp[-3] dp[-2] 或 dp[-1] 不是⼀个有效的数据。因此我们需要在填表之前，将 1, 2, 3 位置的值初始化。根据题意，dp[1] = 1，dp[2] = 2，dp[3] = 4 。

#：填表顺序：

         毫无疑问是「从左往右」。
#： 返回值：
        应该返回 dp[n] 的值。

C++ 算法代码

        使用⼀维数组： 
class Solution {
public:int waysToStep(int n) {// 处理边界情况if(n == 1 || n == 2) return n;if(n == 3) return 4;// 1、创建 dp 表vector<int> dp(n + 1, 0);// 2、初始化dp[1] = 1, dp[2] = 2, dp[3] = 4;// 3、填表for(int i = 4; i <= n; i++)dp[i] = ((dp[i - 1] + dp[i - 2]) % 1000000007 + dp[i - 3]) % 1000000007;// 4、返回return dp[n];}
};

复杂度分析

  • 时间复杂度：O(n)。
  • 空间复杂度：O(n)。

【空间优化 - 滚动数组】

        通过上述图可以发现。

        dp[i]是只与前三个元素相关，所以我们可以将代码写为如下：

C++ 算法代码

class Solution {
public:int waysToStep(int n) {// 1、创建 dp 表vector<int> dp(4, 0);// 2、初始化dp[1] = 1, dp[2] = 2, dp[3] = 4;// 处理边界情况if(n <= 3) return dp[n];// 3、填表uint64_t tmp = 0;for(int i = 4; i <= n; i++){tmp = ((dp[1] + dp[2]) % 1000000007 + dp[3]) % 1000000007;dp[1] = dp[2], dp[2] = dp[3], dp[3] = tmp;}// 4、返回return tmp;}
};

复杂度分析

  • 时间复杂度：O(n)。
  • 空间复杂度：O(1)。

3、使用最小花费爬楼梯⭐

 746. 使用最小花费爬楼梯 - 力扣（LeetCode）

​

【题目解析一】

        pd[i]是由前两个台阶的，所处台阶需花费用 + 所处台阶已花费用的min值。 需要注意的是，此处的顶部并不是n，而是n+1。

【算法原理一】

#：状态表示：

        这道题可以根据「经验 + 题目要求」直接定义出状态dp[i] 表示：到达 i 位置时的最小花费。（注意：到达 i 位置的时候，i 位置的钱不需要算上，先到达，后出发花费）

#： 状态转移方程：
根据最近的⼀步，分情况讨论：
  1. 先到达 i - 1 的位置，然后支付 cost[i - 1] ，接下来走⼀步走到 i 位置：dp[i - 1] + csot[i - 1] 
  2. 先到达 i - 2 的位置，然后支付 cost[i - 2] ，接下来走⼀步走到 i 位置：dp[i - 2] + csot[i - 2] 
#： 初始化：

         从我们的递推公式可以看出，我们需要先初始化 i = 0、i = 1 位置的值。容易得到 dp[0] = dp[1] = 0 ，因为不需要任何花费，就可以直接站在第 0 层和第 1 层上。

#：填表顺序：

        根据「状态转移方程」可得，遍历的顺序是「从左往右」 。
#： 返回值：
         根据「状态表示以及题目要求」，需要返回 dp[n] 位置的值。

C++ 算法代码

        使用⼀维数组： 
class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {// 1、创建dp表vector<int> dp(cost.size() + 1, 0);// 2、初始化dp[0] = 0, dp[1] = 0;// 3、填表for(int i = 2; i <= cost.size(); i++)dp[i] = min(cost[i - 1] + dp[i - 1], cost[i - 2] + dp[i - 2]);// 4、返回return dp[cost.size()];}
};

复杂度分析

  • 时间复杂度：O(n)。
  • 空间复杂度：O(n)。

【空间优化 - 滚动数组一】

        通过上述图可以发现。

        dp[i]是只与前两个元素相关，所以我们可以将代码写为如下：

C++ 算法代码

class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {// 处理边界情况if(cost.size() == 2) return min(cost[0], cost[1]);// 1、创建dp表vector<int> dp(2, 0);// 2、初始化dp[0] = 0, dp[1] = 0;// 3、填表int tmp = 0;for(int i = 2; i <= cost.size(); i++){tmp = min(cost[i - 1] + dp[1], cost[i - 2] + dp[0]);dp[0] = dp[1], dp[1] = tmp;}// 4、返回return tmp;}
};

复杂度分析

  • 时间复杂度：O(n)。
  • 空间复杂度：O(1)。

【题目解析二】

        相对于题目解析一，此处是倒着来的，如：从 n - 1 位置出发，到达楼顶，就是cost [n-1]。从 n - 2 位置出发，到达楼顶，就是cost [n - 2]。

【算法原理二】

#：状态表示：

        这道题可以根据「经验 + 题目要求」直接定义出状态 dp[i] 表示：从 i 位置出发，到达楼顶，此时的最小花费。
#： 状态转移方程：
根据最近的⼀步，分情况讨论：
  1. 支付 cost[i] ，往后走⼀步，接下来从 i + 1 的位置出发到终点： dp[i + 1] + cost[i]
  2. 支付 cost[i] ，往后走两步，接下来从 i + 2 的位置出发到终点： dp[i + 2] + cost[i]

        我们要的是最小花费，因此 dp[i] = min(dp[i + 1], dp[i + 2]) + cost[i] 。

#： 初始化：
        为了保证填表的时候不越界，我们需要初始化最后两个位置的值，结合状态表示易得： dp[n - 1] = cost[n - 1], dp[n - 2] = cost[n - 2]。

#：填表顺序：

        根据「状态转移方程」可得，遍历的顺序是「从右往左」 。
#： 返回值：
         根据「状态表示以及题目要求」，需要返回 min(dp[0], dp[1])  位置的值。

C++ 算法代码

        使用⼀维数组： 
class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {// 处理边界情况if(cost.size() == 2) return min(cost[0], cost[1]);int n = cost.size();// 1、创建dp表vector<int> dp(n, 0);// 2、初始化dp[n - 1] = cost[n - 1], dp[n - 2] = cost[n - 2];// 3、填表for(int i = n - 3; i >= 0; i--)dp[i] = min(dp[i + 1], dp[i + 2]) + cost[i];// 4、返回return min(dp[0], dp[1]);}
};

复杂度分析

  • 时间复杂度：O(n)。
  • 空间复杂度：O(n)。

【空间优化 - 滚动数组二】

        通过上述图可以发现。

        dp[i]是只与后两个元素相关，所以我们可以将代码写为如下：

C++ 算法代码

class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {// 处理边界情况if(cost.size() == 2) return min(cost[0], cost[1]);// 1、创建dp表vector<int> dp(2, 0);// 2、初始化dp[1] = cost[cost.size() - 1], dp[0] = cost[cost.size() - 2];// 3、填表int tmp = 0;for(int i = cost.size() - 3; i >= 0; i--){tmp = min(dp[0], dp[1]) + cost[i];dp[1] = dp[0], dp[0] = tmp;}// 4、返回return min(dp[0], dp[1]);}
};

复杂度分析

  • 时间复杂度：O(n)。
  • 空间复杂度：O(1)。

总结

#：一般的一维线性dp

        状态表示是以 i 为结尾 / 以 i 为起点，然后研究问题  ——  然后就是要看能否，可以推出可行的状态转移方程。

（强行定义状态表示，直接推状态转移方程，就算错了也会有些许思路，答案慢慢的就出来了）


http://chatgpt.dhexx.cn/article/u4VNsiKW.shtml

相关文章

动态规划入门详解 内含12道经典动态规划编程题

动态规划入门详解 内含12道经典动态规划编程题

动态规划入门详解 一 什么是动态规划&#xff1f;&#xff1f; 算法导论中介绍&#xff0c;动态规划和分治方法类似&#xff0c;都是听过子问题的解来解决原问题。下面说一下这2者之间的分别&#xff0c;分治方法将原问题划分为互不相交的子问题&#xff0c;而后将子问题组合…
阅读更多...
【刷题日记】动态规划经典题目

【刷题日记】动态规划经典题目

&#x1f600;大家好&#xff0c;我是白晨&#xff0c;一个不是很能熬夜&#x1f62b;&#xff0c;但是也想日更的人✈。如果喜欢这篇文章&#xff0c;点个赞&#x1f44d;&#xff0c;关注一下&#x1f440;白晨吧&#xff01;你的支持就是我最大的动力&#xff01;&#x1f4…
阅读更多...
Linux命令-sftp文件传输

Linux命令-sftp文件传输

搭建SFTP服务详见博文&#xff1a;https://blog.csdn.net/cen50958/article/details/90722874 连接SFTP 可使用&#xff1a;sftp --help 查看SFTP的连接参数 [rootstudy ~]# sftp --help usage: sftp [-1Cv] [-B buffer_size] [-b batchfile] [-F ssh_config] [-o ssh_option…
阅读更多...
Linux命令(三)：SFTP

Linux命令(三)：SFTP

目录 1、登录 2、文件上传 3、文件下载 4、删除文件/文件夹 5、实战 1、登录 sftp userip 你要用sftp, 当然得登录到sftp服务器&#xff0c; 在linux的shell中执行上面的命令后&#xff0c; linux shell会提示用户输入密码&#xff0c; 我们就输入password吧。 这样就成功…
阅读更多...
Linux常用命令——sftp命令

Linux常用命令——sftp命令

在线Linux命令查询工具(http://www.lzltool.com/LinuxCommand) sftp 交互式的文件传输程序 补充说明 sftp命令是一款交互式的文件传输程序&#xff0c;命令的运行和使用方式与ftp命令相似&#xff0c;但是&#xff0c;sftp命令对传输的所有信息使用ssh加密&#xff0c;它还…
阅读更多...
SFTP命令常用操作

SFTP命令常用操作

SFTP相关(等价于rz/sz&#xff0c;此方式适用于没有工具的情况下&#xff0c;前提是保证sftp默认端口22开放) lcd 本地文件路径 进入到本地的某个目录下 cd 远程文件路径 进入到远程的某个目录下 lpwd 显示本地的当前目录的路径 pwd 显示远程的当前目录的路径 这里只介绍常…
阅读更多...
SFTP基本功之get、put命令操作

SFTP基本功之get、put命令操作

简述 在安装好linux系统之后&#xff0c;开始不断安装部署各种工具&#xff0c;其中很多工具版本太老使得无法使用wget下载&#xff0c;而只能用put命令从本地硬盘中上传之linux系统内安装&#xff0c;而当我编写系统克隆mongodb数据库时&#xff0c;又了解到了get命令&#x…
阅读更多...
SFTP命令的使用，sftp传文件

SFTP命令的使用，sftp传文件

背景&#xff1a;从Windows系统向类unix系统传送文件&#xff0c;使用Windows系统自带的SFTP命令进行文件传送(不用下载F开头&#xff0c;X开头的ftp工具) 背景分割线 上干货&#xff1a;1.WinX&#xff0c;按A&#xff0c;输入SFTP root192.168.162.236 回车&#xff1b; &…
阅读更多...
SFTP登录及命令行用法

SFTP登录及命令行用法

sftp命令行登录过程 ① sftp xxx.xxx.xxx.xxx 登录&#xff08;默认root用户&#xff09;&#xff0c;若指定用户 sftp bluexxx.xxx.xxx.xxx 进行登录&#xff08;blue为用户名&#xff09; ② 登录成功后&#xff0c;会提示输入 密码 ③ 然后&#xff0c;可进入目录&#xf…
阅读更多...
SFTP命令用法（上传和下载 ）

SFTP命令用法（上传和下载 ）

一、SFTP SFTP是Secure File Transfer Protocol的缩写&#xff0c;安全文件传送协议。可以为传输文件提供一种安全的网络的加密方法。SFTP与FTP有着几乎一样的语法和功能。SFTP为SSH的其中一部分&#xff0c;是一种传输档案至Blogger伺服器的安全方式。其实在SSH软件包中&…
阅读更多...
Linux基础命令 sftp命令的使用

Linux基础命令 sftp命令的使用

SFTP&#xff08;Secure File Transfer Protocol&#xff0c;安全文件传输协议&#xff09;是一种基于可靠数据流&#xff08;data stream&#xff09;&#xff0c;提供文件存取和管理的网络传输协议&#xff0c;与 FTP 协议相比&#xff0c;SFTP 在客户端与服务器间提供了一种…
阅读更多...
sftp常用命令介绍

sftp常用命令介绍

sftp常用命令&#xff1a; 1. sftp 登录sftp服务器 sftp userip ​​​​​​ 如需要看全部命令&#xff1a;则使用help即可 2. pwd和lpwd 、 ls和lls 、cd和lcd 等 sftp登录之后默认操作是远程服务器&#xff0c;当需要操作本地时&#xff0c;就需要在前边加“l”&#…
阅读更多...
Linux中使用sftp的常用命令

Linux中使用sftp的常用命令

前言 在数据库远程维护的过程中&#xff0c;经常需要和本机进行数据的交互&#xff0c;常用的交互方式为ftp&#xff0c;但是这种方式需要确保21端口和ftp服务都存在。在远程访问服务器的时候大部分使用ssh来进行连接&#xff0c;其使用的端口为22端口&#xff0c;与之共用的数…
阅读更多...
单链表的基本操作-查找

单链表的基本操作-查找

【问题描述】 实现有头结点单链表查找算法&#xff1a;根据关键字值查找其在单链表中的位置(第一次出现的位置)。 【输入形式】 第一行输入整数n&#xff08;n不大于1000&#xff09;&#xff0c;表示单链表长度&#xff1b; 第二行输入若干个整数&#xff08;以非法整数或…
阅读更多...
单链表的基本操作(C语言+图解分析)

单链表的基本操作(C语言+图解分析)

目录 一、单链表的建立 1、头插法 2、尾插法 二、插入结点操作 三、删除节点操作 四、单链表操作的一些常见问题 1、结构体变量和结构体指针的区别&#xff1f; 2、什么时候要malloc&#xff1f; 3、形参里面出现了取地址符(&)&#xff0c;有什么作用&#xff1f;…
阅读更多...
c++单链表的基本操作（全）

c++单链表的基本操作（全）

俩个基本插入方法 #include <bits/stdc.h> using namespace std; typedef struct LNode { int date; //节点的数据域 struct LNode *next; //节点的指针域 }LNode,*LinkList; // LinkList 为指向结构体LNode的指针类型bool Initlist_L(LinkList &L) …
阅读更多...
单链表的基本操作（学习总结）

单链表的基本操作（学习总结）

单链表的声明初始化&#xff1a; 1.头文件&#xff1a; 这里不做太多说明&#xff0c;是学习C语言的基础。 #include<stdio.h> #include<stdlib.h> 2.结构声明&#xff1a; 数据结构算法中&#xff0c;每个表&#xff0c;树&#xff0c;图类的工具组都需要定义它…
阅读更多...
Java 实现单链表的基本操作

Java 实现单链表的基本操作

顺序表&#xff1a;物理上逻辑上都连续&#xff1b; 链表&#xff1a;物理上不一定连续&#xff0c;逻辑上一定连续的。 链表的概念及结构 概念&#xff1a;连表示一种物理存储结构上非连续、非顺序的存储结构&#xff0c;数据元素的逻辑顺序是用过链表中的引用链接次序实现的…
阅读更多...
数据结构：单链表的基本操作

数据结构：单链表的基本操作

单链表是一种链式存取的数据结构&#xff0c;用一组地址任意的存储单元存放线性表中的数据元素。这组存储单元可以是连续的&#xff0c;也可以是不连续的。链表中的数据是以结点来表示的&#xff0c;一个结点包含数据域和指针域&#xff0c;数据域用来存储结点的值&#xff0c;…
阅读更多...
python实现单链表的基本操作

python实现单链表的基本操作

一、单链表 单向链表&#xff08;单链表&#xff09;是链表的一种&#xff0c;其特点是链表的链接方向是单向的&#xff0c;对链表的访问要通过顺序读取从头部开始。单链表是一种链式存取的数据结构&#xff0c;用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是…
阅读更多...
推荐文章

Copyright @ 2022~2023