# 0070. Climbing Stairs
###### tags: `Leetcode` `Easy` `Dynamic Programming`
Link: https://leetcode.com/problems/climbing-stairs/
## 思路
一开始的想法一直是用n=1和n=2，去凑n=3的答案，也就是3 = 1+2 = 2+1，这样就会有四种结果，然后一直在想怎么消除重复的
没有想到因为一次只能走1格/2格，所以只需要```dp[i]=dp[i-1]+dp[i-2]```就可以了，遗憾住了
## Java Code

class Solution {
    public int climbStairs(int n) {
        if(n == 1){
            return 1;
        }
        if(n == 2){
            return 2;
        }
        int[] dp = new int [n];
        dp[0] = 1;
        dp[1] = 2;
        for(int i = 2;i < n;i++){
            dp[i] = dp[i-1]+dp[i-2];
        }
        return dp[n-1];
    }
}

## Result
Runtime: 0 ms, faster than **100.00%** of Java online submissions for Climbing Stairs.
Memory Usage: 35.8 MB, less than **43.47%** of Java online submissions for Climbing Stairs.