Comment on page

# Min Cost Climbing Stairs

ID: 746; easy

class Solution {

public int minCostClimbingStairs(int[] cost) {

int[] minCost = new int[cost.length + 1];

for (int i = 2; i < minCost.length; i++) {

int oneStep = minCost[i - 1] + cost[i - 1];

int twoStep = minCost[i - 2] + cost[i - 2];

minCost[i] = Math.min(oneStep, twoStep);

}

return minCost[minCost.length - 1];

}

}

This is the DP equation:

$minCost[i] = min(minCost[i-1] + cost[i-1], minCost[i-2], cost[i-2])$

For the minimum cost to reach the ith step, we either came from the one-step hop or from the two-step hop (with their corresponding minimum costs as well).

Time complexity: O(n)

Space complexity: O(n)

class Solution {

public int minCostClimbingStairs(int[] cost) {

int downOne = 0;

int downTwo = 0;

for (int i = 2; i < cost.length + 1; i++) {

int oneStep = downOne + cost[i - 1];

int twoStep = downTwo + cost[i - 2];

int tempDownTwo = downOne;

downOne = Math.min(oneStep, twoStep);

downTwo = tempDownTwo;

}

return downOne;

}

}

Similarly, we can improve the space complexity by just using variables instead of the whole array. It become a little more abstract now.

`downOne`

and `downTwo`

represents the minimum cost to reach one step and two steps below the current step that we are taking. Inside the loop, each iteration, `downOne`

is after `downTwo`

. We calculate the minimum and update `downOne`

. Then, `downTwo`

is updated to be the old `downOne`

.Last modified 1yr ago