70.Climbing Stairs.md

LeetCode 70.Climbing Stairs

通过这道题，练习DP做法，备忘录做法

DP

class Solution {
    public int climbStairs(int n) {
        if (n == 1)
            return 1;
        int[] dp = new int[n];
        Arrays.fill(dp, 0);
        dp[n-1] = 1;
        dp[n-2] = 2;

        for (int i = n-3; i >= 0; i--) 
            dp[i] = dp[i+1] + dp[i+2];

        return dp[0];
    }
}

备忘录

class Solution {
    public int climbStairs(int n) {
        if (n == 1)
            return 1;   
        int[] memo = new int[n];
        Arrays.fill(memo, 0);
        memo[n-1] = 1;
        memo[n-2] = 2;
        return helper(memo, 0, n);
    }

    public static int helper(int[] memo, int k, int n) {
        if (memo[k] == 0) {
            memo[k] = helper(memo, k+1, n) + helper(memo, k+2, n);
        }
        return memo[k];
    }
}