只看楼主 举报 #每日一题#-基础-044使用最小花费爬楼梯

• 楼主

  顾杭林

  话题：38

  精华：0

  积分：194

  数组的每个下标作为一个阶梯，第 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 。

  
  

  阅读：543 回复：7 2022-04-14 08:45:55 举报

• 2楼

  王泽宇

  话题：25

  精华：0

  积分：107

  

  

  2022-04-14 09:03:05 举报

  还能输入140字
• 3楼

  王泽宇

  话题：25

  精华：0

  积分：107

  题解：

  

  2022-04-14 15:19:21 举报

  还能输入140字
• 4楼

  颜妙林

  话题：35

  精华：0

  积分：305

  

  2022-04-15 08:20:10 举报

  还能输入140字
• 5楼

  颜妙林

  话题：35

  精华：0

  积分：305

  

  2022-04-15 08:20:23 举报

  还能输入140字
• 6楼

  颜妙林

  话题：35

  精华：0

  积分：305

  

  2022-04-15 08:20:41 举报

  还能输入140字
• 7楼

  颜妙林

  话题：35

  精华：0

  积分：305

  

  2022-04-15 08:21:05 举报

  还能输入140字
• 8楼

  王泽宇

  话题：25

  精华：0

  积分：107

        这是一个不属于动态规划的递归实现：

  

        为什么不属于动态规划呢？因为在上面的这个算法中，如果我4-1做过第3级台阶，已经有第3级台阶的最小状态了，当递归到5-2的时候找到第3级台阶还是会继续往下搜，搜到边界值（0或1）为止，那就会重复计算了。

        我们再来思考动态规划的定义：对于之前的状态不需要重复计算。所以只要用一个列表，在第一次算过第3级台阶的时候，就把它的最小花费存储下来就可以了。因为我们的递归是自顶向下搜索、自底向上回溯的，所以当第i级台阶已经被赋值过一次时，就证明这是之前已经的状态了。

        我们来看使用动态规划能节省多少时间：

        这是图1的算法执行10000次的时间：

  

        这是动态规划的算法执行10000次的时间：

  

        差了近乎100倍，这还是在数据量仅仅是10的情况下。所以说动态规划是一个非常精妙的优化算法。

  
  

        这是动态规划的递归实现：

  

  2022-04-15 09:53:34 举报

  还能输入140字