LeetCode: 746 Min Cost Climbing Stairs

Let’s solve LeetCode 746: Min Cost Climbing Stairs using the provided template, including both iterative and recursive approaches.

Problem

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

Input: cost = [10, 15, 20]
Output: 15
Explanation: You will start at index 1 and pay 15, then climb two steps to reach the top.

Input: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
Output: 6
Explanation: You will start at index 0, and climb one step with cost 1, and then the second step with cost 1.

问题

给定一个整数数组 cost，其中 cost[i] 是爬到第 i 个台阶的费用。一旦你支付了费用，你可以选择爬一个或两个台阶。

你可以从下标为 0 或下标为 1 的台阶开始。

返回到达楼层顶部的最低费用。

例子

输入: cost = [10, 15, 20]
输出: 15
解释: 你可以从索引 1 开始，支付 15，然后爬两步到达顶部。

输入: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
输出: 6
解释: 你可以从索引 0 开始，爬一步，费用为 1，然后爬到第二步，费用为 1。

Iterative Solution

Approach: Dynamic Programming (Bottom-Up) / 动态规划（自底向上）

To solve this problem, we can use dynamic programming (DP) to keep track of the minimum cost required to reach each step. For each step, the minimum cost is the cost of the step itself plus the minimum cost of the previous step or the step before it. We can iterate through the array and compute the minimum cost to reach the top of the staircase.

Approach Explanation / 方法解释

Base Case: The minimum cost to start from the 0th or 1st step is simply the cost of that step.
Recurrence Relation: For each step i, the minimum cost to reach it is:
```
dp[i] = cost[i] + min(dp[i-1], dp[i-2])
```
Result: The result will be the minimum cost between the last two steps, as you can reach the top from either of them.

Iterative Algorithm / 迭代算法

Create a DP array to store the minimum cost to reach each step.
Set dp[0] and dp[1] to cost[0] and cost[1], respectively.
For each step i from 2 to the end of the array:
- Calculate dp[i] as the cost of the current step plus the minimum cost of the previous two steps.
Return the minimum of the last two steps.

Iterative Implementation / 迭代实现

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        n = len(cost)
        dp = [0] * n
        dp[0] = cost[0]
        dp[1] = cost[1]

        for i in range(2, n):
            dp[i] = cost[i] + min(dp[i - 1], dp[i - 2])

        return min(dp[n - 1], dp[n - 2])

Iterative Solution Explanation / 迭代解决方案解释

Initialize the DP Array / 初始化动态规划数组
```
dp = [0] * n
dp[0] = cost[0]
dp[1] = cost[1]
```
- English: We initialize the DP array to store the minimum cost to reach each step. The first two values are set to the cost of the first and second steps.
- Chinese: 我们初始化动态规划数组以存储到达每个台阶的最小费用。前两个值设置为第一个和第二个台阶的费用。
Iterate Through the Array / 遍历数组
```
for i in range(2, n):
   dp[i] = cost[i] + min(dp[i - 1], dp[i - 2])
```
- English: For each step from index 2 onwards, we calculate the minimum cost to reach it by considering the cost of the current step and the minimum cost of the previous two steps.
- Chinese: 对于索引 2 及之后的每个台阶，我们通过考虑当前台阶的费用和前两个台阶的最小费用来计算到达它的最小费用。
Return the Result / 返回结果
```
return min(dp[n - 1], dp[n - 2])
```
- English: The result is the minimum cost between the last two steps.
- Chinese: 结果是最后两个台阶的最小费用。

Recursive Solution

Approach: Recursive Dynamic Programming with Memoization / 带有记忆化的递归动态规划

We can also solve the problem recursively using memoization to avoid recalculating the same subproblems. At each step, we can either move one or two steps forward, and the cost is the minimum of the two options plus the current step cost. Memoization ensures that we don’t recompute the cost for the same step multiple times.

Recursive Algorithm / 递归算法

Use a memoization dictionary to store the minimum cost to reach each step.
For each step i, recursively calculate the minimum cost to reach the step as:
```
cost[i] + min(minCost(i-1), minCost(i-2))
```
Base cases:
- If i == 0 or i == 1, return cost[i].
Recursively calculate the result and store it in the memoization dictionary.

Recursive Implementation / 递归实现

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        memo = {}

        def minCost(i):
            if i == 0 or i == 1:
                return cost[i]
            if i not in memo:
                memo[i] = cost[i] + min(minCost(i - 1), minCost(i - 2))
            return memo[i]

        n = len(cost)
        return min(minCost(n - 1), minCost(n - 2))

Recursive Solution Explanation / 递归解决方案解释

Base Case: Start at Step 0 or 1 / 基本情况：从第 0 或第 1 个台阶开始
```
if i == 0 or i == 1:
   return cost[i]
```
- English: If the current step is 0 or 1, return the cost of that step since there is no previous step to consider.
- Chinese: 如果当前台阶是 0 或 1，返回该台阶的费用，因为没有前一个台阶需要考虑。
Memoization to Store Results / 记忆化存储结果
```
if i not in memo:
   memo[i] = cost[i] + min(minCost(i - 1), minCost(i - 2))
```
- English: Use memoization to store the result for each step to avoid recalculating it.
- Chinese: 使用记忆化来存储每个台阶的结果，以避免重复计算。
Recursive Calls to Calculate the Minimum Cost / 递归调用计算最小费用
```
return memo[i]
```
- English: Recursively calculate the minimum cost for each step and store it in the memoization dictionary.
- Chinese: 递归计算每个台阶的最小费用，并将其存储在记忆化字典中。

Complexity Analysis / 复杂度分析

Time Complexity / 时间复杂度: O(n), where n is the number of steps. Each step is processed only once.
Space Complexity / 空间复杂度:
- Iterative Solution: O(n), due to the space required for the DP array.
- Recursive Solution: O(n), due to the recursion stack and memoization dictionary.

Key Concept / 关键概念

Dynamic Programming / 动态规划: The problem involves breaking down the process into smaller subproblems and using the results of those subproblems to solve the overall problem.
Memoization / 记忆化: Memoization

is used in the recursive solution to avoid recomputing the same subproblem multiple times.

Summary / 总结

English: We can solve the problem of finding the minimum cost to climb stairs using dynamic programming. Both iterative and recursive approaches work effectively, with memoization helping optimize the recursive solution.
Chinese: 我们可以通过使用动态规划解决爬楼梯的最小费用问题。迭代和递归方法都能有效地工作，记忆化有助于优化递归解决方案。

Tips / 提示

English: Always initialize the base cases correctly when working with dynamic programming, as they define the starting points of the solution.
Chinese: 在处理动态规划时，请确保正确初始化基本情况，因为它们定义了解决方案的起点。

5 More Similar Questions / 推荐5问题

Recommended Resources / 推荐资源

English: Practice problems related to dynamic programming to better understand how to break down problems into smaller subproblems.
Chinese: 练习与动态规划相关的问题，以更好地理解如何将问题分解为更小的子问题。

Post Views: 7

CODEBITWAVE