[746. Min Cost Climbing Stairs](https://leetcode.com/problems/min-cost-climbing-stairs/)

--- tags: leetcode --- # [746. Min Cost Climbing Stairs](https://leetcode.com/problems/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 ```cpp= 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 ```cpp= 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 ```cpp= 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 ```cpp= 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 ```cpp= 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