# 70. Climbing Stairs

{% embed url="<https://leetcode.com/problems/climbing-stairs/>" %}

This is a 1D array dynamic programming problem. It can be solved in both Bottom-Up and Top-Down approach.&#x20;

This is a good problem to get started on the basics of 1D DP problems.

## Problem Description

The question is in how many ways we can reach the $$n^{th}$$step. The valid moves are at any given step is 1 or 2 moves. And need to make sure that we do not go out of bounds

## Intuition

### Top Down

<figure><img src="https://1388126071-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MVQ7Ie-PZpN_8yApX0-%2Fuploads%2FB0lon7X35OvehOtL5ufg%2Fimage.png?alt=media&#x26;token=ac9697ec-8e8a-470f-8409-a0073f00c359" alt=""><figcaption></figcaption></figure>

In the above recursion tree, we see there are duplicate computations

<figure><img src="https://1388126071-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MVQ7Ie-PZpN_8yApX0-%2Fuploads%2Fhi0WyAQbOP8cldu3M2SV%2Fimage.png?alt=media&#x26;token=ca1d69dc-9b09-44bb-97eb-3e6014130751" alt=""><figcaption></figcaption></figure>

The dotted lines represent the duplicate computations. In DP, we optimize it by storing them in a cache, so we make sure we compute the value only once and rest of the calls for that function gets picked up from cache.

## Solution

```java
```
