###### tags: `Leetcode` `easy` `dynamic programming` `python` `c++` `Top 100 Liked Questions`

# 70. Climbing Stairs

## [題目來源:] https://leetcode.com/problems/climbing-stairs/

## 題目:
You are climbing a staircase. It takes n steps to reach the top.

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

## 解題想法:
dp[n]: n階可以組合的數量
dp[n]=dp[n-1]+dp[n-2]

## Python:

class Solution(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        #最後希望return ans[n]值 所以array大小要是n+1最後一值才是ans[n]
        ans = [0]*(n+1)
        ans[0]=1
        ans[1]=1
        #i 從2~n
        for i in range(2,n+1):
            ans[i]=ans[i-1]+ans[i-2]
        return ans[n]
        
    

if __name__ == '__main__':
    result = Solution()
    n = 3
    ans = result.climbStairs(n)
    print(ans)

## C++:

#include<iostream>
using namespace std;

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

int main(){
    Solution res;
    int n=5;
    int ans=res.climbStairs(n);
    cout<<ans<<endl;
    return 0;
}