前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >漫谈递归-746. 使用最小花费爬楼梯

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

作者头像
程序员小王
发布2019-03-06 15:37:12
4870
发布2019-03-06 15:37:12
举报
文章被收录于专栏:架构说

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

递归

代码语言:javascript
复制
/**
    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];
    }

动态规划

代码语言:javascript
复制
 // 走到阶梯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]);

 }
本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2019-02-16,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 Offer多多 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 递归
  • 动态规划
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档