---
title: 'LeetCode 70. Climbing Stairs'
disqus: hackmd
---

# LeetCode 70. Climbing Stairs

## Description

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?

## Example

Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

## Constraints

1 <= n <= 45

## Answer

此題可用DP解法，和計算費氏數列的概念一樣。

//2022_03_30
int climbStairs(int n){
    if(n < 3){return n;}
    int i = 0, c1 = 1, c2 = 2, cn = 0;
    for(i = 3; i <= n; i++){
        cn = c1 + c2;
        c1 = c2;
        c2 = cn;
    }
    return cn;
}

也可用公式解來實現，

int climbStairs(int n){   //DP
    int out[n+1] ;   //存取每個階梯有幾種爬法的陣列，+1是給第0個
    if(n == 1){return 1;}
    out[0] = 0;
    out[1] = 1;   //給定初始值
    out[2] = 2;
    if(n>=3){
        for(int i = 3;i <= n;i++){
            out[i] = out[i-1] + out[i-2];   // 由子問題求解原問題
        }
    }
    return out[n];
}

## Link
https://leetcode.com/problems/climbing-stairs/
###### tags: `Leetcode`