forked from neetcode-gh/leetcode
-
Notifications
You must be signed in to change notification settings - Fork 0
/
0070-climbing-stairs.rb
52 lines (44 loc) · 772 Bytes
/
0070-climbing-stairs.rb
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
# Brute Force
def climb_stairs(n)
return 1 if n.zero?
return 0 if n.negative?
climb_stairs(n - 1) + climb_stairs(n - 2)
end
# Memoize
$repeat = []
def climb_stairs(n)
return 1 if n.zero?
return 0 if n.negative?
if $repeat[n].nil?
res = climb_stairs(n - 1) + climb_stairs(n - 2)
$repeat[n] = res
else
res = $repeat[n]
end
res
end
# Bottom up DP approach
def climb_stairs(n)
return 0 if n.zero?
return 1 if n == 1
dp = []
dp[n] = 1
dp[n - 1] = 1
(n - 2).downto(0) do |idx|
dp[idx] = dp[idx + 1] + dp[idx + 2]
end
dp.first
end
# DP without array
def climb_stairs(n)
return 0 if n.zero?
return 1 if n == 1
two = 1
one = 1
(n - 2).downto(1) do
tmp = one
one += two
two = tmp
end
one + two
end