48 lines
955 B
Markdown
48 lines
955 B
Markdown
|
---
|
||
|
|
layout: page
|
||
|
|
title: Climbing Stairs
|
||
|
|
---
|
||
|
|
|
||
|
|
Basically just fib but start dp array at [1,1]
|
||
|
|
|
||
|
|
n=3
|
||
|
|
[1, 1, 2, 3]
|
||
|
|
|
||
|
|
Gotcha's
|
||
|
|
- don't get variable 'i' and 'n' mixed up
|
||
|
|
|
||
|
|
|
||
|
|
|
||
|
|
{% highlight python %}
|
||
|
|
|
||
|
|
def climbStairs(self, n: int) -> int:
|
||
|
|
|
||
|
|
dp = [1,1]
|
||
|
|
|
||
|
|
for i in range(2, n+1):
|
||
|
|
dp.append(dp[i-1]+dp[i-2])
|
||
|
|
|
||
|
|
print(dp)
|
||
|
|
|
||
|
|
return dp[n]
|
||
|
|
|
||
|
|
{% endhighlight %}
|
||
|
|
|
||
|
|
|
||
|
|
The actual fib problem is written like this:
|
||
|
|
|
||
|
|
{% highlight python %}
|
||
|
|
|
||
|
|
class Solution:
|
||
|
|
def fib(self, N: int) -> int:
|
||
|
|
|
||
|
|
dp = [0,1]
|
||
|
|
|
||
|
|
for i in range(2, N+1):
|
||
|
|
dp.append(dp[i-1]+dp[i-2])
|
||
|
|
|
||
|
|
return dp[N]
|
||
|
|
|
||
|
|
{% endhighlight %}
|
||
|
|
|
||
|
|
|