LeetCode 746 | 使用最小花费爬楼梯

题目

题目

动态规划类型的题目，主要是找出初始条件和状态转移公式。由于爬楼花费的精力必然大于0，所以应该有爬到第一阶和第二阶花费的最小精力为爬直接上该级台阶花费的精力。由于一次只能爬一步或两步，所以爬到第i级台阶花费的最小精力应该是爬到第i-1级台阶或i-2级台阶花费的最小精力的较小值加上爬到该级台阶该花费的精力。具体见代码

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

    }
};

关于返回值：最后一级台阶后还要爬一次（走一步）或倒数第二级台阶爬一次（走两步）才会到顶。所以返回二者较小值。