LeetCode算法题目之70.爬楼梯

题目描述：

假设你正在爬楼梯。需要 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 阶

 

解答：

一：递归方式

    public static void main(String[] args) {
//        int n = 1;
//        int n = 4;
//        int n = 5;
        int n = 45;
        System.out.println(climbStairs1(n));
//        System.out.println(climbStairs2_temp(n));
//        System.out.println(climbStairs3(n));

    }
    // 普通递归方式，时间复杂度2的N次方，空间复杂度N
    // n=45时，超时间限制
    public static int climbStairs1(int n) {
        /**
         * 由示例可知，n=1则1种(1)，n=2则2种(1+1,2)，n=3时3种(1+1+1,1+2;2+1)，n=4时5种(2阶时+2;3阶时+1)即(2种+3种)，n=5为n=4的种类数加n=3的种类数
         * 即有爬楼梯方法种数f(n) = f(n-1)+f(n-2)，n>=3
         */
        if(n==1){
            return 1;
        } else if(n==2){
            return 2;
        } else {
            return climbStairs1(n-1) + climbStairs1(n-2);
        }
    }

二：记忆递归方式

    public static void main(String[] args) {
//        int n = 1;
//        int n = 4;
//        int n = 5;
        int n = 45;
//        System.out.println(climbStairs1(n));
        System.out.println(climbStairs2_temp(n));
//        System.out.println(climbStairs3(n));

    }
    // 记忆递归方式，时间复杂度N，空间复杂度N
    // n=44时，超时间限制
    public static int climbStairs2_temp(int n) {
        int[] temp = new int[n+1];
        return climbStairs2(n,temp);
    }
    public static int climbStairs2(int n, int[] temp) {
        /**
         * 有爬楼梯方法种数f(n) = f(n-1)+f(n-2)，n>=3
         *              f(1)=1; f(2)=2
         * 若n=45，则将44时和43时种类数存入数组temp，同理42~3的所有种类数亦被存储，故递归上跳时无需重复计算
         */
        if (temp[n]>0){ // 若计算过n的种类数，则无需计算
            return temp[n];
        }
        if(n==1){
            return 1;
        } else if(n==2){
            return 2;
        } else {
            return climbStairs2(n-1,temp) + climbStairs2(n-2,temp);
        }
    }

三：动态规划方式

    public static void main(String[] args) {
//        int n = 1;
//        int n = 4;
//        int n = 5;
        int n = 45;
//        System.out.println(climbStairs1(n));
//        System.out.println(climbStairs2_temp(n));
        System.out.println(climbStairs3(n));

    }
    // 动态规划方式，时间复杂度N，空间复杂度1
    public static int climbStairs3(int n) {
        /**
         * 1;2; (1+2)3; (2+3)5; (3+5)8; (5+8)13
         * 定义 left right add
         */
        int left=0;
        int right=0;
        int add=1;
        for(int i=1; i<=n; i++){
            right = left; //      0; 1; 1; 2
            left = add; //        1; 1; 2; 3
            add = right+left; /// 1; 2; 3; 5
        }
        return add;
    }