题目描述

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

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

注意:给定 n 是一个正整数。


动态规划最重要的两个概念:最优子结构和无后效性。
其中:

  • 无后效性决定了是否可使用动态规划来解决。
  • 最优子结构决定了具体如何解决。

求解动态规划的核心问题是穷举,这类问题存在「重叠子问题」,如果暴力穷举的话效率会极其低下,所以需要「备忘录」或者「DP table」来优化穷举过程,避免不必要的计算。
可以用递归自顶向下也可以用for循环自底向上
f(x)=f(x−1)+f(x−2)
当前状态的方法总数等于上一个状态的可能性之和


    public static int climbStairs(int n) {
        int[] memo = new int[n + 1];
        return dp(n, memo);
    }

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

    public static void main(String[] args) {
        System.out.println(climbStairs(11));
    }

踩坑记录:

  1. 优化时数组元素个数选择应该是n+1.
  2. 递归时应该抓住递归函数定义,画出递归树,不要将自己代入到递归过程中.
  3. 递归方程等价代换为递归含义.

Q.E.D.