letcode每日一题-使用最小花费爬楼梯

短命女 2022-12-29 06:50 130阅读 0赞

题目描述如下:

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dYNTk5MQ_size_16_color_FFFFFF_t_70][]

方法一:动态规划

在题中每一个阶梯只有两种情况即爬或者不爬，这里我们用一个数组dp存储阶梯的情况，dp\[i\]\[1\]存储爬阶梯消耗的能量，dp\[i\]\[0\]存储不爬消耗的能量,

我们要知道第i层阶梯爬的所需消耗的最小能量，则

dp\[i\]\[0\]=Math.min(dp\[i-1\]\[0\]+cost\[i\],dp\[i-1\]\[1\]+cost\[i\]);

应为一次只能选择爬一阶或者两阶所以第i阶不爬的话，第i-1阶必须要爬，则:

dp\[i\]\[1\]=dp\[i-1\]\[1\]

最后题目的结果则为Math.min(dp\[cost.length-1\]\[0\],dp\[cost.length-1\]\[0\]),代码实现如下:

public int minCostClimbingStairs(int[] cost) {
            //dp[i][0] --不爬  dp[i][1]--爬
            int[][] dp=new int[cost.length][2];
            dp[0][0]=0;
            dp[0][1]=cost[0];
            for(int i=1;i<cost.length;i++){
                dp[i][0]=dp[i-1][1];
                dp[i][1]=Math.min(dp[i-1][0]+cost[i],dp[i-1][1]+cost[i]);
            }
    
            return Math.min(dp[cost.length-1][0],dp[cost.length-1][1]);
        }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dYNTk5MQ_size_16_color_FFFFFF_t_70 1][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dYNTk5MQ_size_16_color_FFFFFF_t_70]: /images/20221120/f2d54eba87c741d3bef2fc30dbda0a2f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dYNTk5MQ_size_16_color_FFFFFF_t_70 1]: /images/20221120/bdf4d05b962744ca8bca8e77111d4a06.png

发表评论取消回复

表情：

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

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

相关阅读

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

给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。算最低花费则：min(d...

深碍√TFBOYSˉ_/ 2024年05月24日 01:32/ 0 赞/ 70 阅读

相关 Java解决使用最小花费爬楼梯

Java解决使用最小花费爬楼梯 01 题目给你一个整数数组 `cost` ，其中 `cost[i]` 是从楼梯第 `i` 个台阶向上爬需要支付的费用。一旦你支付此

以你之姓@/ 2024年02月05日 20:49/ 0 赞/ 1 阅读

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

746. 使用最小花费爬楼梯题干描述解题思路 1. 确定dp数组以及下标的含义 2. 确定递推公式 3. dp数组

╰半夏微凉°/ 2023年10月16日 15:56/ 0 赞/ 48 阅读

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

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

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

相关 letcode每日一题-使用最小花费爬楼梯

题目描述如下: ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV

短命女/ 2022年12月29日 06:50/ 0 赞/ 131 阅读

相关【必备算法】动态规划：LeetCode题（一）：70.爬楼梯，746. 使用最小花费爬楼梯

[70.爬楼梯¹][70.] 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？注意：给定 n

Dear 丶/ 2022年12月16日 13:25/ 0 赞/ 211 阅读

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

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

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

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

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

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

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

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

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

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

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

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