746 使用最小花费爬楼梯（递推）

电玩女神 2022-09-10 10:16 176阅读 0赞

**1. 问题描述：**

数组的每个下标作为一个阶梯，第 i 个阶梯对应着一个非负数的体力花费值 cost\[i\]（下标从 0 开始）。每当你爬上一个阶梯你都要花费对应的体力值，一旦支付了相应的体力值，你就可以选择向上爬一个阶梯或者爬两个阶梯。请你找出达到楼层顶部的最低花费。在开始时，你可以选择从下标为 0 或 1 的元素作为初始阶梯。

**示例 1：**

输入：cost = \[10, 15, 20\]  
输出：15  
解释：最低花费是从 cost\[1\] 开始，然后走两步即可到阶梯顶，一共花费 15 。

**示例 2：**

输入：cost = \[1, 100, 1, 1, 1, 100, 1, 1, 100, 1\]  
输出：6  
解释：最低花费方式是从 cost\[0\] 开始，逐个经过那些 1 ，跳过 cost\[3\] ，一共花费 6 。

**提示：**

cost 的长度范围是 \[2, 1000\]。  
cost\[i\] 将会是一个整型数据，范围为 \[0, 999\] 。  
来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/min-cost-climbing-stairs

**2. 思路分析：**

分析题目可以知道这是一道简单的**递推**问题，我们可以定义一个一维数组或者列表dp，其中dp\[i\]表示跳到位置i花费的最小代价，怎么样进行状态的计算呢？状态计算对应集合的划分，由题目可以知道我们可以将集合划分为两个部分，分别是i - 2和i - 1位置对应的状态，我们可以从这两个状态转移到当前的状态，最后对两个位置取一个min即可，表示跳到阶梯顶的最小花费。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXV6aGFuZ196eQ_size_9_color_FFFFFF_t_70_g_se_x_16][]

**3. 代码如下：**

from typing import List
    
    
    class Solution:
        def minCostClimbingStairs(self, cost: List[int]) -> int:
            n = len(cost)
            dp = [0] * (n + 2)
            dp[0] = 0
            dp[1] = cost[0]
            for i in range(2, n + 1):
                dp[i] = min(dp[i - 2], dp[i - 1]) + cost[i - 1]
            return min(dp[n - 1], dp[n])

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXV6aGFuZ196eQ_size_9_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/4f6e5b98d2ed448db901c97ca2596d49.png