X

曜彤.手记

随手写写,关于互联网技术、产品与创业

LeetCode 每日一题 - 70. Climbing Stairs


LeetCode 每日一题系列,今天第八题。这是一道读题不用费力、理解十分简单的题目。问题很清晰,但是解决的过程就需要一些思考了。建议先看原题的链接自己做一下,然后再参考本文给出的分析与解答进行总结。【Dynamic Programming】

70. Rotate Array

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

0. 题目大意:

假设你正在爬一个楼梯,该楼梯有 n 阶,而你有两种爬法,每次爬一阶或者两阶。那么请问你有多少种爬法能够到达楼梯顶部?

1. 通用方法,递归:

抛出性能问题不考虑,对于基本上来说所有的“爬楼梯”问题都可以用递归来解决。递归的模式很清晰,每一次爬楼梯都会有两种选择,两种选择之后又是各有两种选择,以此类推。当剩余台阶数量为2时有两种选择:一次爬一阶爬两次,或者一次爬两阶爬一次;而对于剩余台阶数量为1时只有一种爬法:爬一阶一次。算法时间复杂度 “O(nk)”。代码如下所示:

public static int climbStairs(int n) {
    if (n == 1) {  // 只剩一阶时只有一种走法;
        return 1;
    }

    if (n == 2) {  // 剩两阶时有两种走法;
        return 2;
    }

    return climbStairs(n - 1) + climbStairs(n - 2);  // 递归;
}

2. 优化的方法 — Fibonacci:

如果擅于发现规律,你会发现爬楼梯的方法数量随着楼梯阶数 n 的增长正对应着 Fibonacci 数列的第 n+2 项的值,Fibonacci(斐波那契)数列如下:0 1 1 2 3 5 8 13 …,即从第三项开始,该项为前两项的和。这里使用三个变量来实现 Fibonacci 数列。算法时间复杂度 “O(n)”。代码如下所示:

public static int climbStairsOptimize(int n) {
    int a = 0;
    int b = 1;
    int sum = 0;

    for (int i = 0; i < n; i++) {
        sum = a + b;
        a = b;
        b = sum;
    }

    return sum;
}

3. 使用数组的实现:

这里使用数组来实现 Fibonacci 数列,为了节省内存,我们并没有把所有的 Fibonacci 数列全部放入数组,对应的我们只是获取需要的部分数列,这也是在使用“动态规划”算法时优化内存的技巧。

public static int climbStairsOptimizeArray(int n) {
    int[] arr = new int[3];

    arr[0] = 1;  
    arr[1] = 1;  

    for (int i = 2; i <= n; i++) {  
        arr[i%3] = arr[(i-1)%3] + arr[(i-2)%3];  
    }  

    return arr[n%3]; 
}


这是文章底线,下面是评论
  暂无评论,欢迎勾搭 :)