做题之前我们需要先搞清楚解决动态规划的几个步骤
1 状态表示，准备一个dp表
2 状态转移方程
3 初始化
4 填表
5 返回值
步骤1 状态表示，准备dp表
| dp[0] |
| dp[1] |
| dp[2] |
| dp[3] |
| dp[4] = dp[0]+dp[1]+dp[3] |
步骤2 状态转移方程表示
dp[i] = dp[i-1]+dp[i-2]+dp[i-3]
步骤3 4 5 都是对代码的细节处理，代码如下
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<string.h>
int ret(int n)
{
int dp[38] = { 0 };
int i = 0;
if (n == 0)
return 0;
if (n == 1 || n == 2)
return 1;
dp[0] = 0, dp[1] = dp[2] = 1;
for (i = 3; i < n+1; i++)
dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
return dp[n];
}
int main()
{
int n = 0;
scanf("%d", &n);
printf("%d", ret(n));
return 0;
}
根据上面两个图所示，我们可以得到到楼顶的最小花费文章来源：https://www.toymoban.com/news/detail-773954.html
dp[i] = min(dp[i-1]+cost[i-1] ,dp[i-2]+cost[i-2])文章来源地址https://www.toymoban.com/news/detail-773954.html
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];
}
};到了这里，关于动态规划解决泰波那契数列，爬楼梯最小花费问题的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
