509. 斐波那契数 (opens new window)

70. 爬楼梯 (opens new window)

这两道题目都可以用动态规划来解答。

动态规划的本质就是找到递推公式。

动态规划是自底向上的思维方式。而递归是自顶向下的思维方式。

初学者一定要体会这两种思维的差别。

1. 爬楼梯

第n个台阶只能从第n-1台阶 OR第 n- 2台阶上来。

所以,到第n个台阶的走法 = 到第n-1个台阶的走法 + 到第n-2个台阶的走法.

此时递归公式已经浮出水面。

另外我们知道，第1个台阶只有一种走法，第2个台阶有2种走法，这样一来，我们的初始状态也有了。

1.1 朴素动态规划

 public int climbStairs(int n) {
        if(n < 3){
            return n;
        } 
      int[] dp = new  int[n+1];

      dp[1] = 1;
      dp[2] = 2;

      for(int i = 3;i<= n; i++){
          dp[i] = dp[i-1]+dp[i-2];
      }
      return dp[n];
    }

1.2 进阶

根据递推公式可知，f(n)只依赖于f(n-1)和f(n-2)。即我们只需要记住两个状态即可。 所以有必要进行空间优化。

 public int climbStairs(int n) {
        if(n < 3){
            return n;
        }

        int[] dp = new int[2];
        dp[0] = 1;
        dp[1] = 2;

        int sum = 0;

        for(int i = 3; i <= n; i++){
            sum = dp[0]+dp[1];
            dp[0] = dp[1];
            dp[1] = sum;
        }

        return dp[1];
    }