708151. Min Cost Climbing Stairs
Min Cost Climbing Stairs
Slug: min-cost-climbing-stairs
Difficulty: Medium
Id: 708151
Topic Tags: Dynamic Programming
Company Tags: None
Summary
Given a list of integers representing the cost to climb each step, find the minimum total cost to climb n stairs. The cost to climb the first k steps is not necessarily equal to the cost to climb the last k steps.
The problem involves dynamic programming and optimization techniques to solve this problem efficiently.
Detailed Explanation
To solve this problem, we can use dynamic programming. We will create a table dp of size n+1, where dp[i] represents the minimum total cost to climb i stairs.
We initialize dp[0] and dp[1] with the base cases: dp[0] = 0 (no cost to climb 0 stairs) and dp[1] = cost[0] (cost to climb 1 stair).
Then, for each step from i=2 to n, we calculate the minimum total cost by considering two options:
- Climb one step:
dp[i-1] + cost[i-1] - Climb two steps:
dp[i-2] + cost[i-2]
We choose the option with the minimum total cost and store it in dp[i].
Finally, we return dp[n] as the minimum total cost to climb n stairs.
Here is a step-by-step breakdown of the solution:
public int minCostClimbingStairs(int[] cost) {
int n = cost.length;
int[] dp = new int[n+1];
dp[0] = 0;
for (int i = 1; i <= n; i++) {
dp[i] = Math.min(dp[i-1]+cost[i-1], i > 1 ? dp[i-2]+cost[i-2] : 0);
}
return dp[n];
}