746.min-cost-climbing-stairs 使用最小花费爬楼梯

题目描述

746.使用最小花费爬楼梯

解题思路

相当于爬楼梯的进阶版，递推关系变复杂了一些，但本质没有变。
\(a_n = min(a_{n - 1} + cost[i - 1], a_{n - 2} + cost[i - 2])\)
写出递推关系后就能很方便地写出for循环来遍历求解。

代码

#include <vector>
using std::vector;
class Solution {
  public:
    int minCostClimbingStairs(vector<int> &cost) {
        int sz = cost.size();
        vector<int> dp(2);
        dp[0] = dp[1] = 0;
        // dp[2] = cost[0] < cost[1] ? cost[0] : cost[1];
        for (int i = 2; i <= sz; i++) {
            // 原始版本
            // dp[i] = (dp[i - 2] + cost[i - 2]) < (dp[i - 1] + cost[i - 1]) ? (dp[i - 2] + cost[i - 2]) : (dp[i - 1] + cost[i - 1]);
            // 空间优化版本：
            int res = dp[0] + cost[i - 2] < dp[1] + cost[i - 1] ? dp[0] + cost[i - 2] : dp[1] + cost[i - 1];
            dp[0] = dp[1];
            dp[1] = res;
        }
        return dp[1];
    }
};