746. Min Cost Climbing Stairs Easy

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.

Example 1:
Input: cost = [10,15,20]
Output: 15
Explanation: You will start at index 1.

• Pay 15 and climb two steps to reach the top.
  The total cost is 15.

Example 2:
Input: cost = [1,100,1,1,1,100,1,1,100,1]
Output: 6
Explanation: You will start at index 0.

• Pay 1 and climb two steps to reach index 2.
• Pay 1 and climb two steps to reach index 4.
• Pay 1 and climb two steps to reach index 6.
• Pay 1 and climb one step to reach index 7.
• Pay 1 and climb two steps to reach index 9.
• Pay 1 and climb one step to reach the top.
  The total cost is 6.

Approach

Input: An integer array representing the cost to pay for each step.

Output: Minimum cost to climb to the top, climbing 1 or 2 steps each time.

This problem belongs to Linear DP problems.

State Definition

dp[i] represents the minimum cost to climb to the i-th floor.

State Transition

We can reach the i-th floor in two ways:

• Step one step from i - 1: cost is dp[i - 1] + cost[i - 1]
• Step two steps from i - 2: cost is dp[i - 2] + cost[i - 2]

So the state transition equation is: dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])

The final answer is dp[n].

Implementation

python

from typing import List

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        # Array length specifies end boundary combinations accurately counting limits
        n = len(cost)
        # Array dp tracks minimal calculation constraints resolving values correctly effectively
        # Length is n + 1 as evaluating accurately jumps over the top cleanly
        dp = [0] * (n + 1)

        # Generating dp sums calculating accurately elements from step configurations properly resolving index 2
        for i in range(2, n + 1):
            # Select combinations analyzing elements comparing steps efficiently exactly minimum
            # Tracking valid operations limiting efficiently
            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])
        
        # Calculate exactly configurations returning target constraints solving accurately effectively complete
        return dp[n]

javascript

/**
 * @param {number[]} cost
 * @return {number}
 */
var minCostClimbingStairs = function(cost) {
    const dp = Array(cost.length + 1).fill(0);

    for (let i = 2; i < cost.length + 1; i++) {
        dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
    }

    return dp[cost.length];
};

Complexity Analysis

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

Links

746. Min Cost Climbing Stairs (English)

746. 使用最小花费爬楼梯 (Chinese)