70. 爬楼梯

题目链接：爬楼梯

package com.leetcode.simple;

public class _70_爬楼梯 {
    public static void main(String[] args) {
        int a =45;
        System.out.println(climbStairs2(a));
    }
    //方法1:记忆型递归
    public static int climbStairs(int n) {
        int[] arr = new int[n+1];
        return fn(n, arr);
    }
    public static int fn(int n,int[] arr){
        if(arr[n] > 0){
            return arr[n];
        }
        if(n == 1){
            arr[n] = 1;
        }else if (n == 2){
            arr[n] = 2;
        }else {
            arr[n] = fn(n - 1, arr) + fn(n - 2, arr);
        }
        return arr[n];
    }

    //dp动态规划
    public static int climbStairs2(int n){
        if(n == 1){
            return 1;
        }
        int[] dp = new int[n+1];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i < dp.length; i++) {
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }
}