【Algorithm】三步问题
1.三步问题
1.题目连接
2.算法原理讲解&&代码实现
- 动态规划–线性dp
- 线性表示：
dp[i]:到达第i级台阶一共有多少种选择。
- 状态转移方程
dp[i]=dp[i-1]+dp[i-2]+dp[i-3]
- 线性表示：
class Solution {
public:
int waysToStep(int n) {
if(n==1||n==2)return n;
if(n==3) return 4;
vector<int> dp(n);
for(int i=4;i<=n;i++)
{
dp[i]=dp[i-1]+dp[i-2]+dp[i-3];
}
return dp[n];
}
};2.最小花费爬楼梯
1.题目连接
2.算法原理讲解&&代码实现
方法1
- 动态规划–线性dp
- 线性表示：
dp[i]:到达第i级台阶需要花费多少钱。
- 状态转移方程
dp[i]=min（dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]）
- 线性表示：
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
int n=cost.size();
if(n==1||n==0) return 0;
vector<int> dp(n+1);
dp[0]=0;
dp[1]=0;
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
- 动态规划–线性dp
- 线性表示：
dp[i]:从i级台阶出发，爬到顶需要花费多少钱。
- 状态转移方程
dp[i]=min(dp[i+1]+cost[i],dp[i+2]+cost[i])
- 线性表示：
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
int n=cost.size();
if(n==0||n==1) return 0;
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]+cost[i],dp[i+2]+cost[i]);
}
return dp[0]>dp[1]?dp[1]:dp[0];
}
};3.解码方法
1.题目连接
2.算法原理讲解&&代码实现
- 动态规划–线性dp
- 线性表示：
dp[i]:到达第i个字符一共有多少种解码方式。
- 状态转移方程
dp[i]=dp[i-1]+dp[i-2]
- 线性表示：
class Solution {
public:
int numDecodings(string s) {
int n=sizeof(s);
vector<int> dp(n);
dp[0]=s[0]=!'0';
if(n==1) return dp[0];
if(s[1]!='0'&&s[1]!='0') dp[1]+=1;
int ret=(s[0]-'0')*10+(s[1]-'0');
if(ret>=10&&ret<=26) dp[1]+=1;
for(int i=2;i<n;i++)
{
if(s[i]!='0') dp[i]+=dp[i-1];
int re=(s[i-1]-'0')*10+(s[i]-'0');
if(re>=10&&re<=26) dp[i]+=dp[i-2];
}
return dp[n-1];
}
};本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2024-08-25，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
