爬楼梯（leetcode_070 dp）

57 阅读 0 评论 38 点赞

我是靠谱客的博主复杂眼神，最近开发中收集的这篇文章主要介绍爬楼梯（leetcode_070 dp），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目
非常简单容易理解的线性dp，有n阶台阶，一次爬1或2个，爬到n阶有多少种方法，
有1阶 dp[1]=1
有2阶 dp[2]=2 (1+1 0+2)
依次类推

dp[i]:代表到第i阶台阶的方法，
第i阶台阶可以分别由 i-2 走2步和 i-1走1步到达
dp方程 dp[i]=dp[i-1]+dp[i-2]

最小花费爬楼梯
在上一题原理上+每层台阶的花费

需要注意爬到最高层有2种情况
已经在第n层
在第n-1层可以不需要花费跳过第n层到达最高层，~~有点无语~~

class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
int len=cost.size();
if(len==0)
return 0;
vector<int> dp(len);
dp[0]=cost[0];
dp[1]=cost[1];
for(int i=2;i<len;i++) dp[i]=min(dp[i-1],dp[i-2])+cost[i];
return min(dp[len-1],dp[len-2]);
}
};