18.算法学习之爬楼梯2(字节面试题)“leyu乐鱼体育官网”
作者:leyu乐鱼体育官网 发布时间:2021-12-25 02:35
本文摘要:题目:假设你正在爬楼梯。需要 n 阶你才气到达楼顶。每次你可以爬 1 或 2 个台阶, 可是不能一连跳两步(不能两次都是爬2阶)。 你有几多种差别的方法可以爬到楼顶呢?注意:给定 n 是一个正整数。示例:输入: 3 输出: 3 解释: 有三种方法可以爬到楼顶。 1. 1 阶 + 1 阶 + 1 阶2. 1 阶 + 2 阶3. 2 阶 + 1 阶我的思路: 首先大家可以看下我的上篇文章,是爬楼梯的基础版。该字节面试题,在基础版本上做了一些限制,不能两次一连爬2阶。

乐鱼体育官网登录

题目:假设你正在爬楼梯。需要 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.,算,法学,乐鱼平台,习之,爬,楼梯,字节,面,试题,“,leyu

本文来源:乐鱼平台-www.365calcio.com

电话
086-66507661