@dsadaily

  • Home
  • Tags
  • About
  • TryMe

Minimum Cost Climbing Stairs

Return the minimum cost to reach the top of the floor by climbing the stairs either 1 or 2 steps at a time.

Problem Statement

LeetCode-746: You are given an integer array cost where cost[i] is the cost of $i^{th}$ step on a staircase. Once you pay the cost, you can either climb one or two steps.

You can either start from the step with index 0, or the step with index 1. Return the minimum cost to reach the top of the floor.

Approach

To minimize the cost for $i^{th}$ step, we can either come from the $i-1^{th}$ step or the $i-2^{nd}$ step; i.e. choose the minimum of the two. We can define a recurrence relation for the problem as follows:

The above mentioned recurrence relation can be solved using dynamic programming. We can define an array of size n+1 where n is the length of the cost array.

The minCost[i] will store the minimum cost to reach the $i^{th}$ step. The base cases are:

  1. minCost[0] = cost[0]
  2. minCost[1] = cost[1]

Implementation

Here is a java implementation of the above approach:

public int minCostClimbingStairs(int[] cost) {
    int n = cost.length;
    int[] minCost = new int[n];

    minCost[0] = cost[0];
    minCost[1] = cost[1];

    for(int i=2; i < n ; i++){
        minCost[i] = cost[i] + Math.min(minCost[i-1], minCost[i-2]);
    }

    return Math.min(minCost[n-1], minCost[n-2]);
}

Complexity Analysis

The time complexity for the above approach is $O(n)$ where $n$ is the length of the cost array. The space complexity is also $O(n)$ as we are using an array of size n to store the minimum cost to reach the $i^{th}$ step.

Be notified of new posts. Subscribe to the RSS feed.