动态规划

斐波那契类型

  • 使用最小花费爬楼梯

    难度：简单

    给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。 你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。 请你计算并返回达到楼梯顶部的最低花费
    示例 1：
    输入：cost = [10,15,20]
    输出：15
    解释：你将从下标为 1 的台阶开始。- 支付 15 ，向上爬两个台阶，到达楼梯顶部。总花费为 15 。

    示例 2：
    输入：cost = [1,100,1,1,1,100,1,1,100,1]
    输出：6
    解释：你将从下标为 0 的台阶开始。
    支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。
    支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。
    支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。
    支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。
    支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。
    支付 1 ，向上爬一个台阶，到达楼梯顶部。
    总花费为 6 。

  • 方法一

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    class Solution(object):
      def minCostClimbingStairs(self, cost):
          """
          :type cost: List[int]
          :rtype: int
          """
          a = 0
          b = 0
          for i in range(0,len(cost)):
              tem = min(a,b)+cost[i]
              a = b
              b = tem
          return min(a,b)

    解析
    假设数组 cost 的长度为 n，则 n 个阶梯分别对应下标 0 到 n−1，楼层顶部对应下标 n，问题等价于计算达到下标 n 的最小花费。可以通过动态规划求解。 创建长度为 n+1 的数组 dp，其中 dp[i] 表示达到下标 i 的最小花费。 由于可以选择下标 0 或 1 作为初始阶梯，因此有 dp[0]=dp[1]=0。 当 2≤i≤n 时，可以从下标 i−1 使用 cost[i−1] 的花费达到下标 i，或者从下标 i−2 使用 cost[i−2] 的花费达到下标 i。为了使总花费最小，dp[i] 应取上述两项的最小值，因此状态转移方程如下： dp[i]=min(dp[i−1]+cost[i−1],dp[i−2]+cost[i−2])依次计算 dp 中的每一项的值，最终得到的 dp[n] 即为达到楼层顶部的最小花费。

    复杂度分析
    时间复杂度：O(n)，其中 n 是数组 cost 的长度。需要依次计算每个 dp 值，每个值的计算需要常数时间，因此总时间复杂度是 O(n)。
    空间复杂度：O(1)。使用滚动数组的思想，只需要使用有限的额外空间。