746. 使用最小花费爬楼梯

746. 使用最小花费爬楼梯

题目描述

数组的每个下标作为一个阶梯，第 i 个阶梯对应着一个非负数的体力花费值 cost[i]（下标从 0 开始）。
每当你爬上一个阶梯你都要花费对应的体力值，一旦支付了相应的体力值，你就可以选择向上爬一个阶梯或者爬两个阶梯。
请你找出达到楼层顶部的最低花费。在开始时，你可以选择从下标为 0 或 1 的元素作为初始阶梯。

原题链接：

https://leetcode-cn.com/problems/min-cost-climbing-stairs/

示例1：

输入：cost = [10, 15, 20]
输出：15
解释：最低花费是从 cost[1] 开始，然后走两步即可到阶梯顶，一共花费 15 。

示例2：

输入：cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
输出：6
解释：最低花费方式是从 cost[0] 开始，逐个经过那些 1 ，跳过 cost[3] ，一共花费 6 。

提示：

1. cost 的长度范围是 [2, 1000]。
2. cost[i] 将会是一个整型数据，范围为 [0, 999] 。

基本思想（动态规划）

步骤一：
确定状态：
1.逆向思维，考虑最后一步。
2.将问题分解为若干个小的子问题。

本题步骤：迈上最后一个阶梯i只能是从i-1阶或者是i-2阶到达。因此要求爬上第i阶的最小体力值就是第i-1阶和第i-2阶的较小者。由此得出规律，并将大的问题化简为了小的子问题。

步骤二：
得出状态转移方程：

dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])

步骤三：
开始和边界条件：

根据题中所给条件：*可以选择从下标为 0 或 1 的元素作为初始阶梯。*因此可将dp[0]=dp[1]=0作为初值处理。cost的长度是>=2的，i从2开始计算，直到i等于cost的长度截止。

步骤四：
计算顺序：

若根据递归思想从最大的问题dp[i]入手显然会消费大量的时间和空间，并且会超时。本题因采用滚动数组的思想，从小的子问题dp[2]入手，循环计算到dp[i]得出最终结果。

AC代码：

int minCostClimbingStairs(int* cost, int costSize){
    int dp[costSize + 1];
    dp[0] = dp[1] = 0;
    for (int i = 2; i <= costSize; i++) {
        dp[i] = fmin(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
    }
    return dp[costSize];
}

这里采用数组dp来存储每一步计算的数据，消耗内存较大，根据本题的特点，dp[i]取决于dp[i-1]和dp[i-2]，因此可以仅用两个变量来循环记录dp[i-1]和dp[i-2]的值，便可大大节省空间。

空间优化代码如下：

int minCostClimbingStairs(int* cost, int costSize){
    int a= 0, b = 0,c;
    for (int i = 2; i <= costSize; i++) {
        c= fmin(b+ cost[i - 1], a+ cost[i - 2]);
        a= b;
        b= c;
    }
    return b;
}