Problem 70: Climbing Stairs

https://leetcode.com/problems/climbing-stairs/

思路

经典问题，一维的 DP 问题。总的思路是一样的。

public class Solution {
    public int climbStairs(int n) {
        if (n <= 1) {
            return 1;
        }

        //state
        int[] f = new int[n + 1];

        //initiate
        f[0] = 0;
        f[1] = 1;
        f[2] = 2;

        //function
        for (int i = 3; i <= n; i++) {
            f[i] = f[i - 1] + f[i - 2];
        }
        //answer
        return f[n];
    }
}

易错点

1. 初始化数组

   int[] f = new int[n + 1];

   为什么是n + 1呢？因为是从 0 到 n每个都过一遍。

2. 脚标

   int[] f = new int[n + 1];

   这里的int[n + 1]是数组的大小，而不是最后一个元素，这个一定要注意。

   另外最后一个元素是f[n]

3. 方程的递推关系

   f[i] = f[i - 1] + f[i - 2];

   我原来写的是

   f[i] = f[i - 1] + f[i - 2] + 2;

   认为从i - 1跳过来，包含了一种方法，从i - 2跳过来，又包含了一种方法，其实是不对的。

   要把这个问题想清楚