专栏首页架构说漫谈递归-746. 使用最小花费爬楼梯

漫谈递归-746. 使用最小花费爬楼梯

递归特点:从上到下 动态规划特点:从下到上。

递归

/**
    1步骤

     目标: 找到达到楼层顶部的最低花费
            旁白:假如当cost[i] 位置,继续爬一个阶梯或者爬两个阶梯 消耗能量是一样的。求选择跳跃1个还是跳跃2个

     方式: 每当你爬上一个阶梯你都要花费对应的体力花费值,然后你可以选择继续爬一个阶梯或者爬两个阶梯

            旁白:cost:达到楼层顶部 有2个方式 从cost[n-1], cost[n-2] 

      初四化: 在开始时,你可以选择从索引为 0 或 1 的元素作为初始阶梯

       旁白:  cost[0], cost[1] 默认值 不消耗任何能量



    2.测试
    输入: cost = [10, 15, 20]
    输出: 15

     输入: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
    输出: 6

    3 复杂度
        o(n)
        执行用时: 16 ms, 在Min Cost Climbing Stairs的C++提交中击败了13.76% 的用户
        内存消耗: 7.3 MB, 在Min Cost Climbing Stairs的C++提交中击败了0.00% 的用户
    **/

    int minCostClimbingStairs(vector<int>& cost) {

        vector<int> dp(cost.size()+1,-1);
        return minCostClimbingStairs(cost,dp,cost.size());
    }

      int minCostClimbingStairs(vector<int>& cost,vector<int>& dp,int n) {

        if(n<=1)
        {
          return 0; //如果顶楼是0和层 不需要消耗任能量 
        }  
        if (n ==2)
        {
            return min(cost[0],cost[1]);
        }

        if(dp[n]!=-1)
        {
          return dp[n];
        }

        int one=minCostClimbingStairs(cost,dp,n-1)+cost[n-1];//走过阶梯n 需要消耗能量
        int two =minCostClimbingStairs(cost,dp,n-2)+cost[n-2]; //走过阶梯n 需要消耗能量

        dp[n]=min(one,two); //走到阶梯n+1, 需要消耗能量最小能能量 

        return dp[n];
    }

动态规划

 // 走到阶梯n+1, 需要消耗能量最小能能量  
 //执行用时: 24 ms, 在Min Cost Climbing Stairs的C++提交中击败了6.36% 的用户
//内存消耗: 6.9 MB, 在Min Cost Climbing Stairs的C++提交中击败了0.00% 的用户
 int minCostClimbingStairs2(vector<int>& cost) 
 {
      int n=cost.size();
      vector<int> dp(n,-1); //走过阶梯n 需要消耗能量

      dp[0]=cost[0];
      dp[1]=cost[1];
      for (int i=2;i<cost.size();i++)
      {
         if(dp[i-1]<dp[i-2])
         {
           dp[i]=dp[i-1]+cost[i];
         }else
         {
             dp[i]=dp[i-2]+cost[i];
         }
      }
      //走到阶梯n+1, 需要消耗能量最小能能量 
      return min(dp[n-1],dp[n-2]);

 }

本文分享自微信公众号 - 架构说(JiaGouS)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-02-16

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 最短路径问题

    第一题:求不重复路径的个数 How many possible unique paths are there A robot is located at th...

    程序员小王
  • leetcode求第n个丑数

    编写一个程序,找出第 n 个丑数。 丑数就是只包含质因数 2, 3, 5 的正整数。

    程序员小王
  • 系统设计题(1) 连续5天登录用户(快手)

    但是,由于每一行的 id%100 的结 果是无序的,所以我们就需要有一个临时表,来记录并统计结果。

    程序员小王
  • Golang Leetcode 746. Min Cost Climbing Stairs.go

    dp解法 状态方程:dp[i] =min(dp[i-2]+cost[i-2],dp[i-1]+cost[i-1])

    anakinsun
  • Min Cost Climbing Stairs

    On a staircase, the i-th step has some non-negative cost cost[i] assigned (0 ind...

    卡尔曼和玻尔兹曼谁曼
  • HDUOJ----湫湫系列故事——减肥记I

    湫湫系列故事——减肥记I Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65535/32768...

    Gxjun
  • HDU-3672-Caves

    ACM模版 描述 ? 题解 image.png 代码 #include <iostream> #include <cstdio> #include <cstri...

    f_zyj
  • 深度学习: marginal cost (边际成本)

    在看 Faster R-CNN 论文的时候看到 marginal cost (边际成本) 一词,上网一搜,居然没有人解释过该词在深度学习研究领域的定义。

    JNingWei
  • CCF考试——201609-4交通规划

      G国国王来中国参观后,被中国的高速铁路深深的震撼,决定为自己的国家也建设一个高速铁路系统。   建设高速铁路投入非常大,为了节约建设成本,G国国王决定...

    AI那点小事
  • mysql中int长度的意义

    疑问: mysql的字段,unsigned int(4), 和unsinged int(5), 能存储的数值范围是否相同。如果不同,分别是多大? 答: 无论是i...

    joshua317

扫码关注云+社区

领取腾讯云代金券