1.题目

1. 1137. 第 N 个泰波那契数 - 力扣（LeetCode）
2. 面试题 08.01. 三步问题 - 力扣（LeetCode）

2.题目解答

1.第N个泰波那契数

题目及题目解析

动态规划算法学习

1.状态表示

1. 状态表示 是什么

   状态表示值得是dp表里的值的含义

   

2. 怎么来的

   1. 题目要求
   2. 经验和题目要求
   3. 分析问题的过程中，发现重复子问题

2.状态转移方程

dp[i]等于什么

例如本题直接给出来了：

3.初始化

本质就是：保证填表不越界，根据状态转移方程进行填表

//创建dp表
vector<int> dp(n+1);
//dp初始化
dp[0]=0,dp[1]=dp[2]=1;

4.填表顺序

为了填写当前状态，所需状态已经计算过了

本题的状态为：从左向右

//填表
for(int i =3;i<=n;i++)
{dp[i]=dp[i-1]+dp[i-2]+dp[i-3];
}

5.空间优化

动态规划的空间优化一般都为滚动数组

就是填报的这部分的代码要修改

class Solution {
public:int tribonacci(int n) {// 处理边界问题if (n == 0)return 0;if (n == 1 || n == 2)return 1;// 空间优化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;}
};

代码提交

class Solution {
public:int tribonacci(int n) {//处理边界问题if(n==0){return  0;}if(n == 1||n == 2){return 1;}//创建dp表vector<int> dp(n+1);//dp初始化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];}
};

空间优化

2.三步问题

题目及题目解析

算法学习

这里我们可以找一下这里的规律:

可以发现后面的数和前面的数是为前三个数字之和

所以就可以直接用动态规划进行解决这道题

但是要注意这里没进行一次相加就要对相加的数进行取模

dp[i] = ((dp[i - 1] + dp[i - 2]) % MOD + dp[i - 3]) % MOD

这部分代码如下:

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

代码提交

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