# Links

Go to my solution

Go to the question on LeetCode

# My Thoughts

**What Went Well**

I immediately realized that I had to be looking for a pattern and had to cache/track the results of each iteration.

**What Went Wrong**

Dealing with the first two cases was challenging, and a bug threw off the results by 1 or 2 for each computation. I had to submit eight incorrect answers before the pattern stuck out. When focusing solely on the correlation between n and its result, I overlooked the correlation between the results.

**What I Learned**

I refreshed my memory on the definition of memoization.

**How I Can Improve**

In the future, I recognize the importance of reading the constraints first and will prioritize this in future problems.

**Comments**

Reviewing my previous solution from August, I noticed that using an array significantly improved the runtime. However, it’s important to note that LeetCode’s statistics are inconsistent, and submitting the same answer multiple times may result in significantly different solution statistics for the exact same submission.

If you’d like to laugh check out this submission.

# Algorithm Description

**Memoization -** An optimization technique that makes solutions faster by storing results of previous implementations and recalling that information when the same computation is encountered.

# Solution Statistics

**Time Spent Coding**

13 minutes

**Time Complexity**

O(n) - We must iterate from 3 to n, and since n could be a **large number** the resulting time complexity is O(n).

**Space Complexity**

O(n) - We must store n values in the cache, resulting in the O(n) space complexity.

**Runtime Beats**

80.43% of other submissions

**Memory Beats**

45.87% of other sumbissions

# Solution

1
2
3
4
5
6
7
8
9
10
11
12

class Solution:
def climbStairs(self, n: int) -> int:
cache = {1:1,
2:2}
# First two solutions are already in the cache. Start at the third computation
# Cache is indexed starting a 1, so we must iterate from 3 to n+1
for i in range(3,n+1):
# Each iteration is the sum of the two previous solutions (i-1 and i-2)
cache[i] = cache[i-1] + cache[i-2]
return cache[n]

# Previous Solution

1
2
3
4
5
6
7
8
9
10

class Solution:
def climbStairs(self, n: int) -> int:
ar = [1,2]
# First two solutions are already in the cache. Start at the third computation
# Array is indexed starting a 0, so we must iterate from 2 to n
for i in range(2,n):
ar.append(ar[i-1] + ar[i-2])
return ar[n-1]