30 Day Challenge Day 12 | Leetcode 746. Min Cost Climbing Stairs

题解

Easy

动态规划

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        if(cost.empty()) return 0;
        if(cost.size() == 1) return 0;
        if(cost.size() == 2) return 0;
        
        // dp[i]: For a array with size of i, the min cost.
        vector<int> dp(cost.size()+1);
        
        dp[0] = 0; // starting point no cost
        dp[1] = 0; // starting point no cost
        
        for(int i = 2; i < cost.size()+1; i++) {
            dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]);
        }
        
        return dp[cost.size()];
    }
};

空间优化

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