public class Solution {
    /**
     * @param n: An integer
     * @return: An integer
     */
    public int climbStairs(int n) {
        // write your code here
        if (n == 0 || n == 1) {
            return 1;
        }
        
        //f[x] distinct ways num from step 1 to step x
        // because step x equal to step x - 1 ways + making one more step or step x - 2 ways + making two steps
        //f[x] = f[x - 1] + f[x - 2]
        int[] f = new int[n + 1]; 
        f[0] = 1;
        f[1] = 1;
        
        for (int i = 2; i < n + 1; i++) {
            f[i] = f[i - 1] + f[i - 2];
        }
        
        return f[n];
        
    }
}