LeetCode | Climbing Stairs

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

tag: dynamicprogramming

public class Solution {
    public int climbStairs(int n) {
        if(n == 0) return 0;
        if(n == 1) return 1;
        if(n == 2) return 2;
        
        int[] states = new int[n+1];     //存储状态变量的数组，每个元素代表到 i 有多少种方式
        states[0] = 0;                   
        states[1] = 1;                   //只能走1步
        states[2] = 2;                   //走 1+1 、2，共两种方式
        
        //状态转移方程
        //最后一步有两种方式，即走1步或2步
        //走一步的话，前面就有i-1步需要走，共有states[i-1]种方式
        //走两步的话，前面就有i-2步需要走，共有states[i-2]种方式
        //取和，即为到达i有多少种方式
        for(int i=3; i<=n; i++){
            states[i] = states[i-1] + states[i-2];
        }                                            
        
        return states[n];
    }
}