C++ - Min Cost Climbing Stairs

Problem Statement

You are given an array cost[] where cost[i] represents the cost of stepping on the i-th stair.

You can either start from step 0 or step 1.

You can take one step or two steps at a time.

Find the minimum cost required to reach the top.

Example 1:

Input: cost = {10, 15, 20}  

Output: 15  

Explanation:  

- Start from `step 1` (cost = `15`), then jump to the top.  

- Total cost = `15`.  

Example 2:

Input: cost = {1, 100, 1, 1, 1, 100, 1, 1, 100, 1}  

Output: 6  

Explanation:  

- Start at `step 0` → `1 → 1 → 1 → 1 → 1`.  

- Total cost = `6`.  

Approach 1: Dynamic Programming (O(N) Time, O(N) Space)

Define dp[i] as minimum cost to reach step i.

Transition:

dp[i]=cost[i]+min(dp[i−1],dp[i−2])

The answer is min(dp[n-1], dp[n-2]).

Code Implementation

#include <iostream>

#include <vector>

using namespace std;

int minCostClimbingStairs(vector<int>& cost) {

    int n = cost.size();

    vector<int> dp(n + 1, 0);

    for (int i = 2; i <= n; i++) {

        dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);

    }

    return dp[n];

}

int main() {

    vector<int> cost = {10, 15, 20};

    cout << "Minimum Cost: " << minCostClimbingStairs(cost) << endl;

    return 0;

}

Time Complexity:

O(N) (Iterate once through cost[]).

Space Complexity:

O(N) (Extra dp[] array).

Approach 2: Optimized Dynamic Programming (O(N) Time, O(1) Space)

Instead of using an array, use two variables (prev1, prev2).

Update values dynamically to reduce space usage.

Code Implementation

#include <iostream>

#include <vector>

using namespace std;

int minCostClimbingStairs(vector<int>& cost) {

    int n = cost.size();

    int prev1 = 0, prev2 = 0;

    for (int i = 2; i <= n; i++) {

        int curr = min(prev1 + cost[i - 1], prev2 + cost[i - 2]);

        prev2 = prev1;

        prev1 = curr;

    }

    return prev1;

}

int main() {

    vector<int> cost = {1, 100, 1, 1, 1, 100, 1, 1, 100, 1};

    cout << "Minimum Cost: " << minCostClimbingStairs(cost) << endl;

    return 0;

}