动态规划解决泰波那契数列,爬楼梯最小花费问题
做题之前我们需要先搞清楚解决动态规划的几个步骤
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
根据上面两个图所示,我们可以得到到楼顶的最小花费
dp[i] = min(dp[i-1]+cost[i-1] ,dp[i-2]+cost[i-2])
class Solution {public: int minCostClimbingStairs(vector
文章版权声明:除非注明,否则均为
谢士广博客
原创文章,转载或复制请以超链接形式并注明出处。
还没有评论,来说两句吧...