LeetCode746. 使用最小花费爬楼梯

比眉伴天荒 2022-05-19 03:24 132阅读 0赞

数组的每个索引做为一个阶梯，第 `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。

**注意：**

1.  `cost` 的长度将会在 `[2, 1000]`。
2.  每一个 `cost[i]` 将会是一个Integer类型，范围为 `[0, 999]`。

--------------------

思路：当前最小体力花费=min(距当前位置一阶梯的最小体力花费+走一阶梯的体力花费，距当前位置两阶梯的最小体力花费+走两阶梯的体力花费)；

class Solution {
        public int minCostClimbingStairs(int[] cost) {
           int step[]=new int[1024];
            step[0]=0;
            step[1]=0;
            if(cost.length==0) {
            	return 0;
            }
            if(cost.length==1) {
            	return cost[0];
            }
            if(cost.length==2) {
            	return Math.min(cost[0], cost[1]);
            }
            for(int i=2;i<=cost.length;i++) {
            	step[i]=Math.min(step[i-1]+cost[i-1], step[i-2]+cost[i-2]);
            }
        	return step[cost.length];
        }
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，132人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode-746. 使用最小花费爬楼梯

题目来源 [746. 使用最小花费爬楼梯][746.] 动态规划动态规划五部曲 1.确定dp数组以及下标的含义使用动态规划，就要有一个数组来记录状态，

系统管理员/ 2024年03月26日 16:28/ 0 赞/ 8 阅读

相关 leetcode.746. 使用最小花费爬楼梯

746. 使用最小花费爬楼梯数组的每个索引作为一个阶梯，第 `i`个阶梯对应着一个非负数的体力花费值 `cost[i]`(索引从0开始)。每当你爬上一个阶梯你都要花

Love The Way You Lie/ 2022年12月29日 09:19/ 0 赞/ 117 阅读

相关 leetcode【746-使用最小花费爬楼梯】思考、优化、改进

声明：该系列是我的随笔，会记录一些刷题的感受，思路。文章难免有错误或语句不够严谨，欢迎指

灰太狼/ 2022年10月28日 12:27/ 0 赞/ 142 阅读

相关 leetcode 746 使用最小花费爬楼梯

前言题目：[746. 使用最小花费爬楼梯][746.] 参考题解：[使用最小花费爬楼梯-代码随想录][-] -------------------- 提交代码

拼搏现实的明天。/ 2022年09月16日 05:55/ 0 赞/ 109 阅读

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

1. 问题描述：数组的每个下标作为一个阶梯，第 i 个阶梯对应着一个非负数的体力花费值 cost\[i\]（下标从 0 开始）。每当你爬上一个阶梯你都要花费对应的体力值，一

电玩女神/ 2022年09月10日 10:16/ 0 赞/ 107 阅读

相关 746. 使用最小花费爬楼梯

数组的每个下标作为一个阶梯，第 i 个阶梯对应着一个非负数的体力花费值 cost\[i\]（下标从 0 开始）。每当你爬上一个阶梯你都要花费对应的体力值，一旦支付了相应的体

- 日理万妓/ 2022年08月31日 07:20/ 0 赞/ 112 阅读

相关 LeetCode746. 使用最小花费爬楼梯

数组的每个索引做为一个阶梯，第 `i`个阶梯对应着一个非负数的体力花费值 `cost[i]`(索引从0开始)。每当你爬上一个阶梯你都要花费对应的体力花费值，然后你可以选择继

比眉伴天荒/ 2022年05月19日 03:24/ 0 赞/ 133 阅读

相关 LeetCode 746. 使用最小花费爬楼梯

数组的每个索引做为一个阶梯，第 `i`个阶梯对应着一个非负数的体力花费值 `cost[i]`(索引从0开始)。每当你爬上一个阶梯你都要花费对应的体力花费值，然后你可以选择继

古城微笑少年丶/ 2022年05月18日 02:59/ 0 赞/ 129 阅读

相关 leetcode 746. 使用最小花费爬楼梯(python)

数组的每个索引做为一个阶梯，第 `i`个阶梯对应着一个非负数的体力花费值 `cost[i]`(索引从0开始)。每当你爬上一个阶梯你都要花费对应的体力花费值，然后你可以选择继

桃扇骨/ 2022年04月22日 06:42/ 0 赞/ 148 阅读

相关 leetcode：746. 使用最小花费爬楼梯（java dp）

数组的每个索引做为一个阶梯，第 i个阶梯对应着一个非负数的体力花费值 cost[i](索引从0开始)。每当你爬上一个阶梯你都要花费对应的体力花费值，然后你可以

朴灿烈づ我的快乐病毒、/ 2021年09月28日 07:26/ 0 赞/ 248 阅读