使用最小花费爬楼梯-746

数组的每个下标作为一个阶梯，第 i 个阶梯对应着一个非负数的体力花费值 cost[i]（下标从 0 开始）。

每当你爬上一个阶梯你都要花费对应的体力值，一旦支付了相应的体力值，你就可以选择向上爬一个阶梯或者爬两个阶梯。

请你找出达到楼层顶部的最低花费。在开始时，你可以选择从下标为 0 或 1 的元素作为初始阶梯。

示例 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 。

提示：

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

思路

按照评论区的说法，可以先改写下题目：

每个阶梯都有一定重量的屎，一次只能跨一个或者两个阶梯，走到一个阶梯就要吃光上面的屎，问怎么走到楼顶才能吃最少的屎？

开局你选前两个阶梯的其中一个作为起点，并吃光该阶梯的屎。

我们创建一个dp[]数组，里面的值代表：到当前台阶为止，你所吃的最少的屎。

假设有序列cost[] = [10, 15, 20, 21]，则：

• 假设只有 1 级台阶时，则dp[0] = cost[0] = 10，即你到达楼顶怎么样都得吃掉第 0 级台阶上的屎；

• 假设只有 2 级台阶，则dp[1] = min( cost[0], cost[1] )，即你到达楼顶可以跨一步，也可以跨两步；

  • 如果跨一步上楼顶，则吃到第 1 级台阶上的屎：cost[1]；
  • 如果跨两步上楼顶，则吃掉第 0 级台阶上的屎：cost[0]；
  • dp[1]选择这两种方案中吃屎最少的那一种，就上面的序列而言dp[1] = cost[0] = 10。

• 假设有 3 级台阶，则到达第 2 级台阶有两种可能：

  • 从第 0 级台阶跨二步来的，这个过程吃了：int one_step2here = cost[0] + dp[0] 多屎；
  • 从第 1 级台阶跨一步来的，这个过程吃了：int two_step2here = cost[1] + dp[1] 多屎；
  • 当前总台阶数只有3级，因为我们可以从第 0 级或第 1 级台阶出发，所以dp[0] = dp[1] = 0x0；
  • 所以 dp[2] = min( one_step2here, two_step2here )，从上述的两种方案中选一个最小的；
• 如果有 i 级台阶，则： %20%3D%20%0A%5Cbegin%7Bcases%7D%0A0%2C%20%26i%20%3D%200%2C1%5C%5C%0Amin%0A%5Cbegin%7Bcases%7D%0Adp(i-1)%20%2B%20cost%5Bi-1%5D%20%5C%5C%0Adp(i-2)%20%2B%20cost%5Bi-2%5D%0A%5Cend%7Bcases%7D%0A%2C%26i%5Cge%202%0A%5Cend%7Bcases%7D%0A#card=math&code=dp%28i%29%20%3D%20%0A%5Cbegin%7Bcases%7D%0A0%2C%20%26i%20%3D%200%2C1%5C%5C%0Amin%0A%5Cbegin%7Bcases%7D%0Adp%28i-1%29%20%2B%20cost%5Bi-1%5D%20%5C%5C%0Adp%28i-2%29%20%2B%20cost%5Bi-2%5D%0A%5Cend%7Bcases%7D%0A%2C%26i%5Cge%202%0A%5Cend%7Bcases%7D%0A)

有了递推公式，我们可以算出到所有台阶吃的最少的屎。

但是题目要求的是到楼顶吃的最少的屎，所以我们最后还要加上一个步骤：

int one_step2top = cost[cost.size()-1] + dp[cost.size()-1];
int two_step2top = cost[cost.size()-2] + dp[cost.size()-2];
return one_step2top < two_step2top ? one_step2top : two_step2top;

代码

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        if(cost.size() == 0)   return 0;
        if(cost.size() == 1)   return cost[0];
        if(cost.size() == 2)   return cost[0] < cost[1] ? cost[0] : cost[1];
        int* dp = new int[cost.size()];
        memset(dp, 0x0, sizeof(int) * cost.size());
        dp[0] = dp[1] = 0x0;
        for(int i = 2; i < cost.size(); i++) {
            int one_step2here = cost[i-1] + dp[i-1];
            int two_step2here = cost[i-2] + dp[i-2];
            dp[i] = one_step2here < two_step2here ? one_step2here : two_step2here;
        }
        int one_step2top = cost[cost.size()-1] + dp[cost.size()-1];
        int two_step2top = cost[cost.size()-2] + dp[cost.size()-2];
        int MIN = one_step2top < two_step2top ? one_step2top : two_step2top;
        delete[] dp;
        return MIN;
    }
};