746. Min Cost Climbing Stairs

---

My Solution

Solution 1: Brute force (TLE)

The Key Idea for Solving This Coding Question

付了 cost[i] 就可以踏上第 i 階。
一次可以爬 1 階或 2 階。
若 cost 的長度為

$n$ ，那麼階梯的編號就是 0 ~ n - 1 則爬到階梯頂端意味著爬到第 n 階。所以，在 cost 尾端加入一個 0 ，可以讓解題與程式碼實作比較順利。

C++ Code

class Solution {
public:
    int minCostClimbingStairs(vector<int> &cost) {
        cost.push_back(0);
        
        return dp(cost, cost.size() - 1);
    }
    
private:
    // dp reutrns the minimum cost to pay 
    // for climbing to step i.
    int dp(vector<int> &cost, int i) {
        if (i == 0) {
            return cost[0];
        }
        
        if (i == 1) {
            return cost[1];
        }
        
        return min(dp(cost, i - 2), dp(cost, i - 1)) + cost[i];
    }
};

Time Complexity

$O(2^n)$

$n$ is the length of cost.

Space Complexity

$O(n)$

Solution 2: Top-down DP

The Key Idea for Solving This Coding Question

C++ Code 1

class Solution {
public:
    int minCostClimbingStairs(vector<int> &cost) {
        unordered_map<int, int> memo;
        
        memo[0] = cost[0];
        memo[1] = cost[1];
        
        cost.push_back(0);
        
        return dp(cost, memo, cost.size() - 1);
    }
    
private:
    // dp reutrns the minimum cost to pay 
    // for climbing to step i.
    int dp(vector<int> &cost, unordered_map<int, int> &memo, int i) {
        auto iter = memo.find(i);
        if (iter != memo.end()) {
            return iter->second;
        }
        
        memo[i] = min(dp(cost, memo, i - 2), dp(cost, memo, i - 1)) + cost[i];
        return memo[i];
    }
};

C++ Code 2

class Solution {
public:
    int minCostClimbingStairs(vector<int> &cost) {
        vector<int> memo(cost.size() + 1, -1);
        
        memo[0] = cost[0];
        memo[1] = cost[1];
        
        cost.push_back(0);
        
        return dp(cost, memo, cost.size() - 1);
    }
    
private:
    // dp reutrns the minimum cost to pay 
    // for climbing to step i.
    int dp(vector<int> &cost, vector<int> &memo, int i) {
        if (memo[i] >= 0) {
            return memo[i];
        }
        
        memo[i] = min(dp(cost, memo, i - 2), dp(cost, memo, i - 1)) + cost[i];
        return memo[i];
    }
};

Time Complexity

$O(n)$

$n$ is the length of cost.

Space Complexity

$O(n)$

Solution 3: Buttom-up DP

The Key Idea for Solving This Coding Question

C++ Code

class Solution {
public:
    int minCostClimbingStairs(vector<int> &cost) {
        vector<int> dp(cost.size() + 1, -1);
        
        dp[0] = cost[0];
        dp[1] = cost[1];
        cost.push_back(0);
        
        for (int i = 2; i < cost.size(); ++i) {
            dp[i] = min(dp[i - 2], dp[i - 1]) + cost[i];
        }
        
        return dp.back();
    }
    
private:
    // dp reutrns the minimum cost to pay 
    // for climbing to step i.
    int dp(vector<int> &cost, vector<int> &memo, int i) {
        if (memo[i] >= 0) {
            return memo[i];
        }
        
        memo[i] = min(dp(cost, memo, i - 2), dp(cost, memo, i - 1)) + cost[i];
        return memo[i];
    }
};

Time Complexity

$O(n)$

$n$ is the length of cost.

Space Complexity

$O(n)$

Solution 4: Buttom-up DP

The Key Idea for Solving This Coding Question

C++ Code

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

Time Complexity

$O(n)$

$n$ is the length of cost.

Space Complexity

$O(1)$

Miscellaneous