This is one of those problems where the clean idea matters more than the amount of code. For 746. Min Cost Climbing Stairs, the solution in this repository is mainly a straightforward implementation solution.
Guide
What?
The first job is to translate the English prompt into state, transition, and stopping conditions. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: straightforward implementation.
Guide
When?
This is the kind of solution you want when the problem has structure hiding inside a messy-looking input. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are rMinCost, minCostClimbingStairs.
Guide
Why?
The point of the implementation is not to make the code longer. It is to avoid doing the same thinking twice.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Start from the smallest reliable state.
- Expand one legal move at a time.
- Cache, count, or merge information as soon as it becomes settled.
- Let the final stored value answer the original question.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(n) to O(n log n), depending on the dominant loop or data structure operation
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
01/**
02On a staircase, the i-th step has some non-negative cost cost[i] assigned (0 indexed).
03
04Once you pay the cost, you can either climb one or two steps. You need to find minimum cost to reach the top of the floor, and you can either start from the step with index 0, or the step with index 1.
05
06Example 1:
07Input: cost = [10, 15, 20]
08Output: 15
09Explanation: Cheapest is start on cost[1], pay that cost and go to the top.
10Example 2:
11Input: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
12Output: 6
13Explanation: Cheapest is start on cost[0], and only step on 1s, skipping cost[3].
14Note:
15cost will have a length in the range [2, 1000].
16Every cost[i] will be an integer in the range [0, 999].
17**/
18
19//TLE
20class Solution {
21public:
22 int rMinCost(vector<int>& cost, int start){
23 if(start >= cost.size()){
24 return 0;
25 }
26 int curCost = cost[start];
27 // cout << curCost << endl;
28 return curCost + min(rMinCost(cost, start+1), rMinCost(cost, start+2));
29 }
30
31 int minCostClimbingStairs(vector<int>& cost) {
32 return min(rMinCost(cost, 0), rMinCost(cost, 1));
33 }
34};
35
36//Runtime: 12 ms, faster than 62.24% of C++ online submissions for Min Cost Climbing Stairs.
37//Memory Usage: 8.8 MB, less than 98.94% of C++ online submissions for Min Cost Climbing Stairs.
38
39class Solution {
40public:
41 int minCostClimbingStairs(vector<int>& cost) {
42 vector<int> costSum = vector<int>(cost.size()+2, 0);
43
44 for(int i = cost.size()-1; i >=0; i--){
45 costSum[i] = cost[i] + min(costSum[i+1], costSum[i+2]);
46 }
47
48 /*
49 the problem states: "reach the top of the floor",
50 it means reaching the -1th floor,
51 and we can go to -1th floor from either 0th or 1st floor,
52 so here we use min(costSum[0], costSum[1])
53 */
54 return min(costSum[0], costSum[1]);
55 }
56};
57
58/**
59Approach #1: Dynamic Programming [Accepted]
60Intuition
61
62There is a clear recursion available: the final cost f[i] to climb the staircase from some step i is f[i] = cost[i] + min(f[i+1], f[i+2]). This motivates dynamic programming.
63
64Algorithm
65
66Let's evaluate f backwards in order. That way, when we are deciding what f[i] will be, we've already figured out f[i+1] and f[i+2].
67
68We can do even better than that. At the i-th step, let f1, f2 be the old value of f[i+1], f[i+2], and update them to be the new values f[i], f[i+1]. We keep these updated as we iterate through i backwards. At the end, we want min(f1, f2).
69**/
70
71/**
72Complexity Analysis
73Time Complexity: O(N) where N is the length of cost.
74Space Complexity: O(1), the space used by f1, f2.
75**/
76
77//Runtime: 8 ms, faster than 99.66% of C++ online submissions for Min Cost Climbing Stairs.
78//Memory Usage: 8.6 MB, less than 100.00% of C++ online submissions for Min Cost Climbing Stairs.
79class Solution {
80public:
81 int minCostClimbingStairs(vector<int>& cost) {
82 int f1 = 0, f2 = 0;
83 for(int i = cost.size()-1; i >= 0; i--){
84 int f0 = cost[i] + min(f1, f2);
85 f2 = f1;
86 f1 = f0;
87 }
88 return min(f1, f2);
89 }
90};Cost