【动态规划】dp之斐波那契数列模型
动态规划有许多模型，根据这些模型可以再细分专题来训练动态规划问题。
第N个泰波那契序数
LeetCode网做题链接：1137. 第 N 个泰波那契数 - 力扣（LeetCode）
思路：
分为五步进行，
第一找出状态表示，这一步需要根据题目要求以及做题经验。以第i个位置为结尾+题目要求。
第二找到状态转移方程，根据最近的一步推导出dp[i]，划分问题
第三初始化，因为有可能导致dp表越界，所以要对dp[1]和dp[0]进行初始化。
第四填表顺序，因为是以i为结尾，所以是从左往右进行填表。
第五是返回dp表。
代码实现：
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];
}
};移动思路：
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;
}
};三步问题
LeetCode做题链接：面试题 08.01. 三步问题 - 力扣（LeetCode）
思路：
分为五步进行，
第一找出状态表示，这一步需要根据题目要求以及做题经验。以第i个位置为结尾+题目要求。
第二找到状态转移方程，根据最近的一步推导出dp[i]，划分问题
第三初始化，因为有可能导致dp表越界，所以要对dp[1]和dp[0]和dp[2]进行初始化。
第四填表顺序，因为是以i为结尾，所以是从左往右进行填表。
第五是返回dp表。
代码实现：
class Solution {
public:
int waysToStep(int n) {
const int N=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])%N +dp[i-3])%N;
}
return dp[n];
}
};细节问题：因为题目说明可能得数会很大，因此需要对结果进行取模操作。
使用最小花费爬楼梯
LeetCode做题链接：746. 使用最小花费爬楼梯 - 力扣（LeetCode）
思路：
分为五步进行，
第一找出状态表示，这一步需要根据题目要求以及做题经验。以第i个位置为起点+题目要求。
第二找到状态转移方程，根据最近的一步推导出dp[i]，划分问题
第三初始化，因为有可能导致dp表越界，所以要对dp[1]和dp[0]和dp[2]进行初始化。
第四填表顺序，因为是以i为起点，所以是从右往左进行填表。
第五是返回dp表。
代码实现：
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
int n=cost.size();
vector<int> dp(n);
dp[n-1]=cost[n-1];dp[n-2]=cost[n-2];
for(int i=n-3;i>=0;i--)
{
dp[i]=min(dp[i+1],dp[i+2])+cost[i];
}
return min(dp[0],dp[1]);
}
};解码方法
LeetCode做题链接：91. 解码方法 - 力扣（LeetCode）
思路：
分为五步进行，
第一找出状态表示，这一步需要根据题目要求以及做题经验。以第i个位置为结尾+题目要求。
第二找到状态转移方程，根据最近的一步推导出dp[i]，划分问题
第三初始化，因为有可能导致dp表越界，所以要对dp[1]和dp[0]和dp[2]进行初始化。
第四填表顺序，因为是以i为结尾，所以是从左往右进行填表。
第五是返回dp表。
代码实现：
class Solution {
public:
int numDecodings(string s) {
int n=s.size();
vector<int> dp(n+1);
dp[0]=1;
dp[1]=s[1-1]!='0';
for(int i=2;i<=n;i++)
{
if(s[i-1]!='0') dp[i]+=dp[i-1];
int t=(s[i-2]-'0')*10+s[i-1]-'0';
if(t>=10 && t<=26)dp[i]+=dp[i-2];
}
return dp[n];
}
};总结：
做题下来发现，规律较为死板，总体分为五步进行，最重要的是找出状态转移方程，写出状态转移方程的重点在于如何找出离结果最近的那几步操作。
学习编程就得循环渐进，扎实基础，勿在浮沙筑高台
腾讯云开发者
