动态规划:从入门到入土系列(一)

🎈个人主页:🎈 :✨✨✨初阶牛✨✨✨
🐻推荐专栏1: 🍔🍟🌯C语言初阶
🐻推荐专栏2: 🍔🍟🌯C语言进阶
🔑个人信条: 🌵知行合一

前言

本篇是动态规划系列的入门基础题,以”第 n 个泰波那契数”和 “三步问题”为例子.

目录

• 前言
• 一、第 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

算法讲解:

1. 创建dp表.
   确定状态表示:用dp[n]表示第 n 个泰波那契数 Tn 的值.
   我们要返回Tn的值,也就是第n个泰波那契数,由于T0的存在(即有第0个泰波那契数),所以我们创建dp表的时候,需要创建n+1个大小的数组,即dp[n+1].
   ·需要设置的文字

2. 初始化.
   前面三个泰波那契数的值题目都已经给出,dp[0]=0,dp[1]=1,dp[2]=1;

3. 填写dp表.
   根据题目介绍,我们不难得出状态转移方程是:Tn+3 = Tn + Tn+1 + Tn+2
   即:Tn = Tn-3 + Tn-2 + Tn-1

本题中是直接给出了状态转移方程,大多数动态规划的题目是需要我们自己推导的.

4. 确认返回值.
   题目要求返回第 n 个泰波那契数 Tn 的值,那dp[n]不就是我们需要返回的吗?
5. 细节处理:
   由于0<n<=2时,无法进行完整的初始化操作,我们可以提前进行判定直接返回.

代码实现:

class Solution {
public:
    int tribonacci(int n) {
        //防止因为n过小导致的初始化问题
        if(n==0) return 0;
        if(n==1||n==2)return 1;

        //1.创建dp表
        int dp[n+1];
        //2.初始化
        dp[0]=0,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];
    }
};

空间优化:

在上面的算法中,我们创建了n+1个大小的数组空间,所以空间复杂度是O(n),我们可以采用滚动数组的方法,将时间复杂度降到O(1).

其实我们可以不用创建n+1个大小的数组空间,因为只需要知道第n项的前三个,就可以推导出第四项,所以我们可以创建只有四个大小的数组空间.

class Solution {
public:
    int tribonacci(int n) {
        //防止因为n过小导致的初始化问题
        if(n==0) return 0;
        if(n==1||n==2)return 1;

        //1.创建dp表
        int dp[4];
        //2.初始化
        dp[0]=0,dp[1]=1,dp[2]=1;
        //3.填表
        for(int i=3;i<=n;i++)
        {
            dp[3]=dp[2]+dp[1]+dp[0];
            //动态更新数组(滚动数组)
            dp[0]=dp[1];
            dp[1]=dp[2];
            dp[2]=dp[3];
        }
        //4.确认返回值
        return dp[3];
    }
};

二、三步问题

题目来源于:力扣
题目链接:传送门

题目描述:

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

示例1:

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

示例2:

输入：n = 5
输出：13

算法讲解:

1. 创建dp表:
   确定状态表示:dp[n]代表有n阶楼梯时,小孩可以选择上楼的方式.
   我们要j计算的是当有n阶台阶时,小孩有多少种上楼梯的方式.
   并且此题规定:0个台阶时,有一种上楼方式.
   所以我们创建dp表的时候,需要创建n+1个大小的数组,即dp[n+1].

2. 初始化:
   上楼梯的方法:dp[0]=1,dp[1]=1,dp[2]=2;

3. 填写dp表.
   先看懂题目意思,此题需要自行推导状态转移方程.
   分析: dp[0]=1,dp[1]=1.

4. 确认返回值:
dp[n]代表有n阶楼梯时,我们可以选择的上楼方式.所以返回dp[n]即可.

5.细节处理:
(1)由于0<n<=2时,无法进行完整的初始化操作,我们可以提前进行判定直接返回.
(2)由于这里数据比较大,所以每次进行”+“运算时,需要进行对结果取模(1000000007).

代码实现:

class Solution {
public:
    int waysToStep(int n) {
        const int MOD =1000000007;
        
        //防止因为n过小导致的初始化问题
        if(n==0||n==1)return 1;
        if(n==2)return 2;
		
		//创建dp数组
        int dp[n+1];
        //初始化操作
        dp[0]=1,dp[1]=1,dp[2]=2;
        //填表
        for(int i=3;i<=n;i++)
        {
            dp[i]=((dp[i-3]+dp[i-2])%MOD+dp[i-1])%MOD;//这里一定要记得取模
        }
        //返回值
        return dp[n];
    }
};

运行结果:

当然也可以使用滚动数组的方式进行空间优化,这里就不再演示了.

三、 结语:

本篇是动态规划系列的入门基础题,题目难度偏简单,后续会慢慢更新,难度有所提升.
下篇见!