做网站设计制作的,如何做网站搬家,直接通过域名访问wordpress,个人博客主页代码题目描述#xff1a; 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢#xff1f;
示例 1#xff1a;
输入#xff1a;n 2
输出#xff1a;2
解释#xff1a;有两种方法可以爬到楼顶。
1. 1 阶…题目描述 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢
示例 1
输入n 2
输出2
解释有两种方法可以爬到楼顶。
1. 1 阶 1 阶
2. 2 阶
示例 2
输入n 3
输出3
解释有三种方法可以爬到楼顶。
1. 1 阶 1 阶 1 阶
2. 1 阶 2 阶
3. 2 阶 1 阶提示
1 n 45
解题准备 1.猜测该题可能涉及的基础操作目前看不出来。 2.拿特殊的题目尝试一下 可以发现第一层台阶非常特殊虽然题目提供两种操作但是我们只能爬1步因此只有1种方案。 3.筛查题目条件题目仅一个输入表示有几层台阶。其为我们提供两个操作一次爬升一楼或一次爬升两楼。 4.理解假设我们想爬第n层台阶要不从n-1层开始爬要不从n-2层开始爬【除了n1的情况题目提供n1】 5.猜测由此可以猜测想知道第n层台阶有几种爬法极大可能和n-2n-1这两层台阶有关。
解题难点1分析 虽然猜测n层台阶与n-1、n-2可能有关系但是未证实其难点是找到关系内容。 1如何找到三者的关系 我们的目标是找到爬n层的所有方案虽然只要求给出方案的数目假设采用穷举法。 假设num【x】表示爬第x层的所有方案数目。使x2【以下的所有数据默认不超出限制】 当nx时x-1到x是一种方案x-2到x也是一种方案。忽略其它单单最后一步一共有两种方案。 面对x-1x-3到x-1可以走2步x-2到x-1可以走1步。同样是两种方案。 如果爬到x-1和x-2的所有方案num【x-1】和num【x-2】之间没有重复的序列就可以证明num【x】num【x-1】num【x-2】。 2如何证明x-1和x-2之间一定不存在重复 对于x-11st.如果x-1是从x-3直接跳到x-1那么掠过x-2不存在重复。【x-3到达x-2也是一个步骤】 2nd.如果x-1从x-2爬升到x-1那么由于x-2到x-1多一步骤故不重复。
至此证明完毕。
递归代码
class Solution {public int climbStairs(int n) {if(n1){return 1;}int[] datanew int[n];data[0]1;data[1]2;return helper(n-1, data);}private int helper(int temp, int[] data){if(temp1){return 2;}else if(temp0){return 1;}if(data[temp-1]0data[temp-2]0){return data[temp-1]data[temp-2];}else if(data[temp-2]0){return helper(temp-1, data)data[temp-2];}else if(data[temp-1]0){return helper(temp-2, data)data[temp-1];}data[temp]helper(temp-1, data)helper(temp-2, data);return data[temp];}
}
以上内容即我想分享的关于力扣热题8的一些知识。 我是蚊子码农如有补充欢迎在评论区留言。个人也是初学者知识体系可能没有那么完善希望各位多多指正谢谢大家。
