DP：斐波那契数列模型
一、第N个泰波那契数
class Solution {
public:
int tribonacci(int n)
{
//边界情况
if(n==0||n==1) return n;
if(n==2) return 1;
//建表
vector<int> dp(n+1);
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];
}
};时间复杂度O（N）,空间复杂度为O（N）
是否还有可以优化的方法呢？？那就是该题可以使用滚动数组！
class Solution {
public:
int tribonacci(int n)
{
//边界情况
if(n==0||n==1) return n;
if(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;
}
};时间复杂度O（N）,空间复杂度为O（1）
二、三步问题
思路1：dp[i]表示从起点到达i位置一共有几种方法
class Solution {
public:
int waysToStep(int n)
{
const int MOD=1e9+7;
//边界情况
if(n==1||n==2) return n;
if(n==3) return 4;
//建立dp表
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];
}
};思路2：dp[i]表示从i位置到达终点一共有几种方法
class Solution {
public:
int waysToStep(int n)
{
const int MOD=1e9+7;
//边界情况
if(n==1||n==2) return n;
if(n==3) return 4;
//建立dp表
vector<int> dp(n);
//初始化
dp[n-1]=1,dp[n-2]=2,dp[n-3]=4;
//填表
for(int i=n-4;i>=0;--i) dp[i]=((dp[i+1]+dp[i+2])%MOD+dp[i+3])%MOD;
return dp[0];
}
};三、使用最小的花费爬楼梯
方法1：dp[i]表示从起点到i台阶的最小花费
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost)
{
int n=cost.size();
vector<int> dp(n+1);
//开始填表
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];
}
};思路2：我们也可以以i为起点，让dp[i]表示到楼顶的最小花费
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]=cost[i]+min(dp[i+1],dp[i+2]);
return min(dp[0],dp[1]);
}
};四、解码方法
class Solution {
public:
int numDecodings(string s)
{
int n=s.size();
vector<int> dp(n);
if(s[0]!='0') ++dp[0];
//处理边界情况
if(n==1) return dp[0];
if(s[1]!='0'&&s[0]!='0') dp[1]++;
int t=(s[0]-'0')*10+(s[1]-'0');
if(10<=t&&t<=26) ++dp[1];
//开始填表
for(int i=2;i<n;++i)
{
if(s[i]!='0') dp[i]+=dp[i-1];
int t=(s[i-1]-'0')*10+(s[i]-'0');
if(10<=t&&t<=26) dp[i]+=dp[i-2];
}
return dp[n-1];
}
};我们会发现dp[1]的初始化和填表里面的过程非常相似，所以我们可以用一个动态规划的小技巧——虚拟节点（专门用来处理边界问题）
class Solution {
public:
int numDecodings(string s)
{
int n=s.size();
vector<int> dp(n+1);
dp[0]=1;
if(s[0]!='0') ++dp[1];
//开始填表
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(10<=t&&t<=26) dp[i]+=dp[i-2];
}
return dp[n];
}
};先暂时更新到这，后面有新的题目会持续更新
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2024-03-22，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录