746. Min Cost Climbing Stairs

📝 Problem Details

• Title: 746. Min Cost Climbing Stairs
• Link: https://leetcode.com/problems/min-cost-climbing-stairs/
• Difficulty: Easy
• Tags/Categories: Dynamic-Programming

input array cost where cost[i] is the cost of the ith step can either climb one or two steps each turn can start from step 0 or step 1 return the min cost to reach the top floor

💭What Were My Initial Thoughts?

1. Can it be broken into subproblems?
	- yes
	- like climbing stairs, to reach step i, we can from from either i-1 or i-2
	- the cost of each step must be accounted for
	- the introduction of cost makes this similar to a Knapsack Problem

2. Choose Top-Down vs. Bottom-Up
	- bottom up is best in this case
	- avoids recursion overhead
	- allows for space optimization

3. Define DP State
	- dp[i] would represent the min cost to reach step[i]
	- since we can start from step 0 or step 1
		- init dp[0] = cost[0], dp[1] = cost[1]

4. Transition Formula
	- dp[i] = min(dp[i−1], dp[i−2]) + cost[i]
	- take the min cost path from i-1 or i-2 and add the current step's cost
	- final state is to reach the top 
		- min(dp[n−1],dp[n−2])
		- because the last step is not counted in cost

5. Optimize for Space
	- like climbing stairs, we only need the last two computations
	- reduces space complexity from O(n) to O(1)

💡 Explanation of Solution

same as initial thoughts

⌛ Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(1)

💻 Implementation of Solution

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();
 
        // base cases:
        int prev2 = cost[0];
        int prev1 = cost[1];
    
        for(int i=2; i < n; i++) {
            int curr = min(prev1,prev2) + cost[i];
            prev2 = prev1;
            prev1 = curr;
        }
 
        return min(prev1, prev2); // min cost to reach the top
    }
};