这篇文章上次修改于 1206 天前，可能其部分内容已经发生变化，如有疑问可询问作者。 > 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？ 注意：给定 n 是一个正整数。 #### 示例 输入： 3 输出： 3 解释： 有三种方法可以爬到楼顶。 1. 1 阶 + 1 阶 + 1 阶 2. 1 阶 + 2 阶 3. 2 阶 + 1 阶 #### 解题思想： 1. 这个是数学归纳方法，从最简单的开始算起，找到规律 2. 第n阶是n-1阶的走法 + 第n-2阶的走法之和，是一个斐波那契 3. 注意这类题是找到他的循环部分即可，不牵涉AI的算法，除了if else就是loop，抓住这道题的loop循环是关键 #### 算法： 1. n=1,和n=2 已知， 2. n>=3 时，记住n-1用的步数和n-2用的步数，分别为f1，f2 3. 第n阶的f3就是f1+f2 ``` java /** * 递推思想 */ private static int climbStairs(int n){ if(n == 1) return 1; if(n == 2) return 2; int f1 = 1; int f2 = 2; int f3 =0; //斐波那契的缓存最近三次的结果 for(int i = 3; i <= n ; i++ ){ f3 = f1 + f2; f1 = f2; f2 = f3; } return f3; } ``` leetcode地址:[https://leetcode-cn.com/problems/climbing-stairs/](https://leetcode-cn.com/problems/climbing-stairs/)
没有评论