假设你正在爬楼梯。需要 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 阶
来源：力扣（LeetCode）
链接：力扣
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
| import java.util.HashMap; import java.util.Map; public class ClimbingStairs {
public int climbStairs(int n) { if(n<=0) { return 0; } else if(n==1) { return 1; }else if(n==2) { return 2; }else { return climbStairs(n-1)+climbStairs(n-2); } }
//看网友答案，递归时可以加点缓存。还以为可行，其实不行 //因为是从后向前倒退的，因为前面几个没有计算，继续倒退 //从小到大累加，才是更快的办法 Map public int climbStairsCache(int n) { if(n<=0) { return 0; } else if(n==1) { return 1; }else if(n==2) { return 2; }else { if(cache.get(n)!=null) { return cache.get(n); } int nValue= climbStairs(n-1)+climbStairs(n-2); cache.put(n, nValue); return nValue; } }
public int climbStairsDp(int n) { if(n<=0) { return 0; } else if(n==1) { return 1; }else if(n==2) { return 2; } //0不用，感觉没有意义 int[] array = new int[n+1]; array[1]=1; array[2]=2; for(int index=3;index<=n;index++) { array[index]=array[index-1]+array[index-2]; } return array[n]; }
public int climbStairsDpTmpVariable(int n) { if(n<=0) { return 0; } else if(n==1) { return 1; }else if(n==2) { return 2; } //0不用，感觉没有意义 int dp1=1; int dp2=2; int dpIndex=0; for(int index=3;index<=n;index++) { //f(x)=f(x-1)+f(x-2) dpIndex=dp1+dp2; //向前滚动，复用变量 dp1=dp2; dp2=dpIndex; } return dpIndex; }
//方法4 矩阵快速幂，方法5 通项公式(纯数学了，艹) } |
| package cn.fansunion.leecode; import org.junit.Assert; import org.junit.Test; import cn.fansunion.leecode.todo.ClimbingStairs; import cn.hutool.core.date.StopWatch; public class ClimbingStairsTest { @Test public void test() { ClimbingStairs cs = new ClimbingStairs(); final int actual45 = 1836311903; StopWatch sw45 = new StopWatch(); sw45.start(); Assert.assertEquals(cs.climbStairs(45), actual45); sw45.stop(); System.out.println("45:"+sw45.getTotalTimeMillis()+"ms"); StopWatch sw37 = new StopWatch(); sw37.start(); Assert.assertEquals(cs.climbStairs(37), 39088169); sw37.stop(); System.out.println("37:"+sw37.getTotalTimeMillis()+"ms"); }
@Test public void testDp() { ClimbingStairs cs = new ClimbingStairs(); final int actual45 = 1836311903; StopWatch sw45 = new StopWatch(); sw45.start(); Assert.assertEquals(cs.climbStairsDp(45), actual45); sw45.stop(); System.out.println("45:"+sw45.getTotalTimeNanos()+"ns"); StopWatch sw37 = new StopWatch(); sw37.start(); Assert.assertEquals(cs.climbStairsDp(37), 39088169); sw37.stop(); System.out.println("37:"+sw37.getTotalTimeNanos()+"ns"); }
@Test public void climbStairsDpTmpVariable() { ClimbingStairs cs = new ClimbingStairs(); final int actual45 = 1836311903; StopWatch sw45 = new StopWatch(); sw45.start(); Assert.assertEquals(cs.climbStairsDpTmpVariable(45), actual45); sw45.stop(); System.out.println("45:"+sw45.getTotalTimeNanos()+"ns"); StopWatch sw37 = new StopWatch(); sw37.start(); Assert.assertEquals(cs.climbStairsDpTmpVariable(37), 39088169); sw37.stop(); System.out.println("37:"+sw37.getTotalTimeNanos()+"ns"); }
@Test public void testCache() { ClimbingStairs cs = new ClimbingStairs(); final int actual45 = 1836311903; StopWatch sw45 = new StopWatch(); sw45.start(); Assert.assertEquals(cs.climbStairsCache(45), actual45); sw45.stop(); System.out.println("45Cache:"+sw45.getTotalTimeMillis()); StopWatch sw37 = new StopWatch(); sw37.start(); Assert.assertEquals(cs.climbStairsCache(37), 39088169); sw37.stop(); System.out.println("37Cache:"+sw37.getTotalTimeMillis()); } } |
总结
这里形成的数列正好是斐波那契数列，答案要求的 f(n)f(n) 即是斐波那契数列的第 nn 项（下标从 00 开始）。我们来总结一下斐波那契数列第 nn 项的求解方法：
nn 比较小的时候，可以直接使用过递归法求解，不做任何记忆化操作，时间复杂度是 O(2^n)O(2
n
)，存在很多冗余计算。
一般情况下，我们使用「记忆化搜索」或者「迭代」的方法，实现这个转移方程，时间复杂度和空间复杂度都可以做到 O(n)O(n)。
为了优化空间复杂度，我们可以不用保存 f(x - 2)f(x−2) 之前的项，我们只用三个变量来维护 f(x)f(x)、f(x - 1)f(x−1) 和 f(x - 2)f(x−2)，你可以理解成是把「滚动数组思想」应用在了动态规划中，也可以理解成是一种递推，这样把空间复杂度优化到了 O(1)O(1)。
随着 nn 的不断增大 O(n)O(n) 可能已经不能满足我们的需要了，我们可以用「矩阵快速幂」的方法把算法加速到 O(log n)O(logn)。
我们也可以把 nn 代入斐波那契数列的通项公式计算结果，但是如果我们用浮点数计算来实现，可能会产生精度误差。
作者：LeetCode-Solution
链接：力扣
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
