使用最小花费爬楼梯
花最少的钱爬到楼顶
cost是在每一阶台阶，往上走的成本。
dp[i]的定义：到达第i个台阶所花费的最少体力为dp[i]。
可以有两个途径得到dp[i]，一个是dp[i-1] 一个是dp[i-2]。因为最多走两步
即从 i-1台阶，花费cost(i-1) 到 i ；和 i-2台阶，花费cost(i-2) 到 i
dp数组如何初始化
dp[i]由dp[i-1]，dp[i-2]推出，既然初始化所有的dp[i]是不可能的，那么只初始化dp[0]和dp[1]就够了，其他的最终都是dp[0]dp[1]推出。
class Solution { public: int minCostClimbingStairs(vector<int>& cost) { vector<int> dp(cost.size()+1); //要到楼顶，要比台阶数多一个 dp[0] = 0; //从初始到第0个台阶，和第1个台阶花钱 dp[1] = 0; for(int i=2 ; i<dp.size() ; i++) //从第二个台阶开始计算最小的成本 { dp[i] = min(dp[i-2]+cost[i-2] , dp[i-1]+cost[i-1]); } return dp[cost.size()]; //到比台阶多一级，即到楼顶的最小成本 } };
二刷
class Solution { public: int minCostClimbingStairs(vector<int>& cost) { if(cost.size() == 2) return min(cost[0] , cost[1]); vector<int> dp(cost.size()+1,0); for(int i=2 ; i<=cost.size() ;i++) { dp[i] = min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]); } return dp[cost.size()]; } };
