【思特奇杯·云上蓝桥-算法集训营】第3周 爬楼梯

【思特奇杯·云上蓝桥-算法集训营】第3周 爬楼梯 爬楼梯

题目描述：

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

暴力递归

    public int climbStairs1(int n) {
        //base case
        if(n<0){
            return 0;
        }
        if(n==0){
            return 1;
        }
        return climbStairs1(n-1)+climbStairs1(n-2);
    }

记忆化搜索

   public int climbStairs(int n){
        int[] dp = new int[n + 1];
        Arrays.fill(dp,-1);
        return process(n,dp);
    }

    private int process(int n, int[] dp) {
        if(n<0){
            return 0;
        }
        if(n==0){
            return 1;
        }
        if(dp[n]!=-1){
            return dp[n];
        }
        dp[n] = process(n-1,dp)+process(n-2,dp);
        return dp[n];
    }

动态规划

    public int climbStairs2(int n) {
        int[] dp = new int[n+1];
        dp[0] = 1;
        dp[1] = 1;
        for(int i=2;i<=n;i++){
            dp[i] = dp[i-1]+dp[i-2];
        }
        return dp[n];
    }