本文主要是介绍动态规划解决泰波那契数列,爬楼梯最小花费问题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
做题之前我们需要先搞清楚解决动态规划的几个步骤
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;
}
根据上面两个图所示,我们可以得到到楼顶的最小花费
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();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];}
};
这篇关于动态规划解决泰波那契数列,爬楼梯最小花费问题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!