写点什么

算法攻关 - 爬楼梯最小花费 _0076

发布于: 2021 年 03 月 16 日
算法攻关-爬楼梯最小花费_0076

一、题目描述

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

 

提示:

cost 的长度范围是 [2, 1000]。

cost[i] 将会是一个整型数据,范围为 [0, 999] 。

来源:力扣(LeetCode)

链接:https://leetcode-cn.com/problems/min-cost-climbing-stairs

著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

二、思考

参考的大神的思路:https://leetcode-cn.com/problems/min-cost-climbing-stairs/solution/yi-bu-yi-bu-tui-dao-dong-tai-gui-hua-de-duo-chong-/

注意题目描述:每当你爬上一个阶梯你都要花费对应的体力值,一旦支付了相应的体力值,你就可以选择向上爬一个阶梯或者爬两个阶梯


所以示例 1 中只花费一个 15 就可以到阶梯顶,最后一步可以理解为 不用花费。


读完题大家应该知道指定需要动态规划的,贪心是不可能了。


确定 dp 数组以及下标的含义

使用动态规划,就要有一个数组来记录状态,本题只需要一个一维数组 dp[i]就可以了。


dp[i]的定义:第 i 个台阶所花费的最少体力为 dp[i]。(注意这里认为是第一步一定是要花费)


对于 dp 数组的定义,大家一定要清晰!


确定递推公式

可以有两个途径得到 dp[i],一个是 dp[i-1] 一个是 dp[i-2]。


那么究竟是选 dp[i-1]还是 dp[i-2]呢?


一定是选最小的,所以 dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i];


注意这里为什么是加 cost[i],而不是 cost[i-1],cost[i-2]之类的,因为题目中说了:每当你爬上一个阶梯你都要花费对应的体力值

根据 dp 数组的定义,dp 数组初始化其实是比较难的,因为不可能初始化为第 i 台阶所花费的最少体力。


那么看一下递归公式,dp[i]由 dp[i-1],dp[i-2]推出,既然初始化所有的 dp[i]是不可能的,那么只初始化 dp[0]和 dp[1]就够了,其他的最终都是 dp[0]dp[1]推出。


所以初始化代码为:

int[] dp(cost.size()); dp[0] = cost[0]; dp[1] = cost[1];

  1. 确定遍历顺序

因为是模拟台阶,而且 dp[i]又 dp[i-1]dp[i-2]推出,所以是从前到后遍历 cost 数组就可以了。


三、代码实现

class Solution {    public int minCostClimbingStairs(int[] cost) {        //初始化状态数组        int[] dp = new int[cost.length];        //处理0和1        dp[0] = cost[0];        dp[1] = cost[1];        //演变递推公式        for (int i = 2; i < cost.length; i++) {            dp[i] = Math.min(dp[i - 1], dp[i - 2]) + cost[i];        }        // 注意最后一步可以理解为不用花费,所以取倒数第一步,第二步的最少值        return Math.min(dp[cost.length - 1], dp[cost.length - 2]);
}}
复制代码

时间复杂度为 O(n)

空间复杂度为 O(n)

上面的代码在空间利用上可以再优化一下。


注意到状态转移方程中只用到了前面的两个记录,可以不用一维数组,只用两个变量保存前面的两个记录,并不断更新,就可以递推下去,这样空间复杂度就是 O(1)了。


更进一步,注意到初始值 dp[0] = cost[0],dp[1] = cost[1],可以直接复用 cost 数组来代表 dp 数组。

class Solution {    public int minCostClimbingStairs(int[] cost) {        //直接利用数组来代表有状态的数组        for (int i = 2; i < cost.length; i++) {            cost[i] = Math.min(cost[i - 2], cost[i - 1]) + cost[i];        }        return Math.min(cost[cost.length - 2], cost[cost.length - 1]);    }}
复制代码

时间复杂度为 O(n)

空间复杂度为 O(1)

四、小结

其实这个题和昨天的爬楼梯都是 DP 动态规划题目,解法还有其他几种,但是我觉得这种比较简单适用。


发布于: 2021 年 03 月 16 日阅读数: 11
用户头像

小胜靠智,大胜靠德 2019.06.27 加入

历经创业、京东、腾讯、滴滴公司,希望能够有些东西一起分享。公众号:小诚信驿站,微信/CSDN搜索:wolf_love666

评论

发布
暂无评论
算法攻关-爬楼梯最小花费_0076