> For the complete documentation index, see [llms.txt](https://emmaguo100.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://emmaguo100.gitbook.io/leetcode/01-30-2022-70.md).

# 01/30/2022 70

Use dynamic programming. The total number of ways to reach i th is equal to sum of ways of reaching ((i−1) th step and ways of reaching (i−2) th step. dp\[i] = dp\[i-1] + dp\[i-2].

Time O(n)

Space O(n)

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

}