题解 | #最小花费爬楼梯#

题目主要信息:

给定一个数组，其中每个元素代表该级楼梯向上爬需要支付的费用，下标从0开始
一旦支付费用，可以任意选择爬一级或是二级
需要求爬到顶楼，即越过数组末尾元素所需要的最小花费
可以从下标为0或是1的台阶开始

举一反三：

学习完本题的思路你可以解决如下题目：

BM62.斐波那契数列

BM63.跳台阶

BM69.把数字翻译成字符串

方法：动态规划（推荐使用）

知识点：动态规划

动态规划算法的基本思想是：将待求解的问题分解成若干个相互联系的子问题，先求解子问题，然后从这些子问题的解得到原问题的解；对于重复出现的子问题，只在第一次遇到的时候对它进行求解，并把答案保存起来，让以后再次遇到时直接引用答案，不必重新求解。动态规划算法将问题的解决方案视为一系列决策的结果

思路：

题目同样考察斐波那契数列的动态规划实现，不同的是题目要求了最小的花费，因此我们将方案统计进行递推的时候只记录最小的开销方案即可。

具体做法：

step 1：可以用一个数组记录每次爬到第i阶楼梯的最小花费，然后每增加一级台阶就转移一次状态，最终得到结果。
step 2：（初始状态） 因为可以直接从第0级或是第1级台阶开始，因此这两级的花费都直接为0.
step 3：（状态转移） 每次到一个台阶，只有两种情况，要么是它前一级台阶向上一步，要么是它前两级的台阶向上两步，因为在前面的台阶花费我们都得到了，因此每次更新最小值即可，转移方程为： $d p [i] = m i n (d p [i - 1] + c o s t [i - 1], d p [i - 2] + c o s t [i - 2])$ 。

图示：

alt

Java实现代码：

import java.util.*;
public class Solution {
    public int minCostClimbingStairs (int[] cost) {
        //dp[i]表示爬到第i阶楼梯需要的最小花费
        int[] dp = new int[cost.length + 1]; 
        for(int i = 2; i <= cost.length; i++)
            //每次选取最小的方案
            dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]); 
        return dp[cost.length];
    }
}

C++实现代码：

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        //dp[i]表示爬到第i阶楼梯需要的最小花费
        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()];
    }
};

Python代码实现：

class Solution:
    def minCostClimbingStairs(self , cost: List[int]) -> int:
        #dp[i]表示爬到第i阶楼梯需要的最小花费
        dp = [0 for i in range(len(cost) + 1)] 
        for i in range(2, len(cost) + 1):
            #每次选取最小的方案
            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]) 
        return dp[len(cost)]

复杂度分析：

时间复杂度： $O (n)$ ，其中 $n$ 为给定的数组长度，遍历一次数组
空间复杂度： $O (n)$ ，辅助数组dp的空间