您好,欢迎进入yb体育官方网站yb体育官方网站电动伸缩门有限公司官网!
yb体育|官方网站

联系我们

邮箱:admin@sixth-element.cn
电话:064-79083805
地址:湖南省怀化市环江毛南族自治县人中大楼877号 在线咨询

公司资讯

18.算法学习之爬楼梯2(字节面试题)

发布日期:2021-12-13 00:43浏览次数:
本文摘要:题目:假设你正在爬楼梯。需要 n 阶你才气到达楼顶。每次你可以爬 1 或 2 个台阶, 可是不能一连跳两步(不能两次都是爬2阶)。 你有几多种差别的方法可以爬到楼顶呢?注意:给定 n 是一个正整数。示例:输入: 3 输出: 3 解释: 有三种方法可以爬到楼顶。1. 1 阶 + 1 阶 + 1 阶2. 1 阶 + 2 阶3. 2 阶 + 1 阶我的思路: 首先大家可以看下我的上篇文章,是爬楼梯的基础版。 该字节面试题,在基础版本上做了一些限制,不能两次一连爬2阶。

yb体育官方网站

题目:假设你正在爬楼梯。需要 n 阶你才气到达楼顶。每次你可以爬 1 或 2 个台阶, 可是不能一连跳两步(不能两次都是爬2阶)。

你有几多种差别的方法可以爬到楼顶呢?注意:给定 n 是一个正整数。示例:输入: 3 输出: 3 解释: 有三种方法可以爬到楼顶。1. 1 阶 + 1 阶 + 1 阶2. 1 阶 + 2 阶3. 2 阶 + 1 阶我的思路: 首先大家可以看下我的上篇文章,是爬楼梯的基础版。

该字节面试题,在基础版本上做了一些限制,不能两次一连爬2阶。那么对于这个限制,我们该怎么做呢? 我们可以想到 :x:爬到第X阶台阶 Y:爬到第X阶时最后爬的台阶数 dp[x][y] = dp[x-1][1] + dp[x-1][2] + dp[x-2][1] ; dp[x-1][2] 不行,因为不能一连爬2次2阶上篇文章我们写到普通版本的爬台阶公式是:f(x) = f(x-1) + f(x-2)这里我们也可以把dp[x][y]转换成fx公式。

dp[x][y] = dp[x-1][1] + dp[x-1][2] + dp[x-2][1] ; 可以转换成如下:f(x -1)<==> dp[x-1][1] + dp[x-1][2] ;f(x-3) <==> dp[x-2][1] ; 因为倒数第二步x-2到x跳两步的话,那么它的前一步肯定是跳一步。所以得:f(x) = f(x-1) + f(x-3);凭据上述分析所以获得代码:public static int climbStairs3(int n) { int[] dp = new int[n]; for (int i = 0; i < n; i++) { if (i < 3) { dp[i] = i + 1; } else { dp[i] = dp[i - 1] + dp[i - 3]; } } return dp[n - 1]; }固然, 我们也可以使用DP数组来解决此类问题。

代码如下:public static int climbStairs2(int n) { if (n < 3) { return n; } //为了更好的阅读,忽略了index为0; int[][] dp = new int[n + 1][3]; dp[1][1] = 1; dp[2][1] = 1; dp[2][2] = 1; for (int i = 3; i <= n; i++) { //走到第I步 跳1步时,所以上一步跳到第I-1时可以调1/2步。dp[i][1] = dp[i - 1][1] + dp[i - 1][2]; //走到第I不 跳2步时,那么跳到第I-2步时其时必须只跳了1步。dp[i][2] = dp[i - 2][1]; } return dp[n][1] + dp[n][2]; }以上为我的全部解答。解决此类DP问题,最重要的就是状态转移方程的分析了。

多思考,多动手。如有错误,请列位大佬指出,谢谢!。


本文关键词:18.,yb体育官方网站,算,法学,习之,爬,楼梯,字节,面,试题,题目

本文来源:yb体育官方网站-www.sixth-element.cn

联系方式

全国服务热线

064-79083805

手 机:14416403956

地 址:湖南省怀化市环江毛南族自治县人中大楼877号

扫一扫,加微信

Copyright © 2000-2021 www.sixth-element.cn. yb体育官方网站科技 版权所有 ICP备91241067号-2 XML地图 织梦模板