leetcode 21天动态规划入门——从0到0.5【Day02】爬楼梯
写在前面
接着上一篇，今天小付可谓是跑上跑下，绕着这个围山而建的学校跑来跑去，为了吃份味道不错的虾仁馅饺子，毕竟今天是冬至啦~也希望各位友友们，也能吃到好吃的饺子，话不多说，接着昨日来到了咱们的第二天，爬楼梯…
DAY2
题目一
- 爬楼梯 难度系数：*
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
示例
示例1:
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
示例2:
输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶
提示
1<= n <=45
思路
接着按照动态规划思路来，以小部分来推断全部的思想。
我们先来进行观察
1、当n = 1时，有一种方法到楼顶
1. 1阶
2、当 n = 2时，有两种方法到达楼顶
1. 1 阶 + 1 阶
2. 2 阶
3、当n = 3 时，有三种方法到达楼顶
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶
4、当n = 4时， 有五种方法到达楼顶
1. 1 阶 + 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶 + 1 阶
3. 2 阶 + 1 阶 + 1 阶
4. 1 阶 + 1 阶 + 2 阶
5. 2 阶 + 2 阶
这下你发现规律没？
因为爬上第n阶楼梯的方法等于
- 爬上第 n - 1阶楼梯的方法再往上爬一层阶梯 也就是
+ 1 - 爬上第n - 2 阶楼梯的方法在往上爬两层阶梯 也就是
+ 2
故此我们可以得到关系式Fn = Fn-1 + Fn-2
剩下的就不用我教了吧 和昨天的动态规划一样 ，模拟一小部分推出全部。
代码实现
class Solution {
public int climbStairs(int n) {
if (n < 3)return n;
int n1 = 1;
int n2 = 2;
int n3 = n1 + n2;
//模拟动态推导
for (int i = 3;i < n;i++){
n1 = n2 ;
n2 = n3 ;
n3 = n1 + n2;
}
return n3;
}
}
执行结果
题目二
- 使用最小花费爬楼梯 难度系数：*
数组的每个下标作为一个阶梯，
第 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] 。
思路
这里 小付 对题 进行了简要概述 抽取关键字
对于很多小伙伴说这道题没看懂 那小付就来给大家做个抽象概念
-
每个阶梯都有一定数量障碍物，一次只能跨一个或者两个阶梯，
走到一个阶梯就要扫清上面的障碍，问怎么走才能遇到最少的障碍走到顶阶？
开局你选前两个阶梯的其中一个作为开头点，并扫清当前阶梯的障碍。
当然最后一个阶梯还存在一个无障碍的阶梯，登峰造极。 -
好了 这下就又到了动态规划的问题了塞 ，还是用小部分进行模拟推导全局。
1、首先我们需要维护一个数组用来记录能到达这个阶梯之前所需要花费的最小体力
2、进行模拟找到动态规划的公式：
能到达当前楼层n的最小化费等于：
- 到达第n - 1层楼层所需体力 + 第n - 1层楼层爬层所需体力的体力总和
- 到达第n - 2层楼层所需体力 + 第n - 2层楼层爬层所需体力的体力总和
- 二者取最小值
sumCost[i] = Math.min(sumCost[i-1]+ cost[i-1],sumCost[i-2]+cost[i-2]);
代码实现
class Solution {
public int minCostClimbingStairs(int[] cost) {
int sumCost[] = new int [cost.length+1];
sumCost[0] = sumCost[1] = 0;
for (int i = 2 ;i< cost.length + 1;i++){
sumCost[i] = Math.min(sumCost[i-1]+ cost[i-1],sumCost[i-2]+cost[i-2]);
}
return sumCost[cost.length];
}
}
执行结果
写在最后
今天是动态规划入门的第二天
坚持打卡
因为现在目前只是入门阶段
所以不要认为题相对简单就对动态规划产生‘简单题’的想法
很基础 咱们 循序渐进
我相信 在21天之后 你会有不小的收货的
最后
每天进步点 每天收获点
愿诸君 事业有成 学有所获
如果觉得不错 别忘啦一键三连哦~