Skip to main content

Fibonacci Series

These problems are the entry point to dynamic programming: linear DP on a single 1-D index, where the state at i depends only on a handful of earlier states. Each one is presented through the same progression - start with the bare recurrence memoized by an LRU cache, make the memo table explicit, turn it bottom-up into a tabulation, then shrink that table to the last few cells for O(k) space. Seeing one recurrence in all four forms is the fastest way to internalize the top-down to bottom-up transformation.

Fibonacci Series Extension​

509. Fibonacci Number​

Easy·
Solutions:
FIG. 509 FIBONACCI NUMBER LRU● INTERACTIVE
Visualize
class Solution:
def fib(self, n: int) -> int:
@lru_cache(maxsize=None)
def recursion(i):
if i <= 1:
return i
else:
return recursion(i - 1) + recursion(i - 2)
 
return recursion(n)

70. Climbing Stairs​

Easy·
Solutions:
FIG. 70 CLIMBING STAIRS LRU● INTERACTIVE
Visualize
class Solution:
def climbStairs(self, n: int) -> int:
@lru_cache(maxsize=None)
def recursion(i):
if i <= 2:
return i
else:
return recursion(i - 1) + recursion(i - 2)
 
return recursion(n)

1137. N-th Tribonacci Number​

Easy·
Solutions:
FIG. 1137 N TH TRIBONACCI NUMBER LRU● INTERACTIVE
Visualize
class Solution:
def tribonacci(self, n: int) -> int:
@lru_cache(maxsize=None)
def recursion(i):
if i == 0:
return 0
elif i <= 2:
return 1
else:
return recursion(i - 1) + recursion(i - 2) + recursion(i - 3)
 
return recursion(n)

Staircase​

Easy·

Description

Solutions:
FIG. STAIRCASE LRU● INTERACTIVE
Visualize
def count_ways(n):
@lru_cache(maxsize=None)
def recursion(i):
if i <= 1:
return 1
elif i == 2:
return 2
else:
return recursion(i - 1) + recursion(i - 2) + recursion(i - 3)
 
return recursion(n)

Number Factors​

Easy·

Description

Solutions:
FIG. NUMBER FACTORS LRU● INTERACTIVE
Visualize
def count_ways(n):
@lru_cache(maxsize=None)
def recursion(i):
if i <= 2:
return 1
elif i == 3:
return 2
else:
return recursion(i - 1) + recursion(i - 3) + recursion(i - 4)
 
return recursion(n)

Min / Max, Top-Down (N to 0)​

746. Min Cost Climbing Stairs​

Easy·
Solutions:
FIG. 746 MIN COST CLIMBING STAIRS LRU● INTERACTIVE
Visualize
class Solution:
def minCostClimbingStairs(self, cost: List[int]) -> int:
@lru_cache(maxsize=None)
def recursion(i):
if i <= 1:
return 0
else:
one_step = cost[i - 1] + recursion(i - 1)
two_steps = cost[i - 2] + recursion(i - 2)
return min(one_step, two_steps)
 
n = len(cost)
return recursion(n)

Minimum Jumps with Fee​

Easy·

Description

Solutions:
FIG. MINIMUM JUMPS WITH FEE LRU● INTERACTIVE
Visualize
def find_min_fee(fee):
@lru_cache(maxsize=None)
def recursion(i):
if i <= 3:
return fee[0]
else:
one_step = fee[i - 1] + recursion(i - 1)
two_steps = fee[i - 2] + recursion(i - 2)
three_steps = fee[i - 3] + recursion(i - 3)
return min(one_step, two_steps, three_steps)
 
n = len(fee)
return recursion(n)

198. House Robber​

Medium·
Solutions:
FIG. 198 HOUSE ROBBER LRU● INTERACTIVE
Visualize
class Solution:
def rob(self, nums: List[int]) -> int:
@lru_cache(maxsize=None)
def recursion(i):
if i < 0:
return 0
else:
robbed = nums[i] + recursion(i - 2)
not_robbed = recursion(i - 1)
return max(robbed, not_robbed)
 
n = len(nums)
return recursion(n - 1)

213. House Robber II​

Medium·
Solutions:
FIG. 213 HOUSE ROBBER II TWO RANGES● INTERACTIVE
Visualize
class Solution:
def rob_simple(self, nums: List[int]) -> int:
@lru_cache(maxsize=None)
def recursion(i):
if i < 0:
return 0
else:
robbed = nums[i] + recursion(i - 2)
not_robbed = recursion(i - 1)
return max(robbed, not_robbed)
 
n = len(nums)
return recursion(n - 1)
 
def rob(self, nums: List[int]) -> int:
if len(nums) == 0:
return 0
elif len(nums) == 1:
return nums[0]
else:
return max(self.rob_simple(nums[1:]), self.rob_simple(nums[:-1]))

Min / Max, Bottom-Up (0 to N)​

Minimum Jumps to Reach the End​

Easy·

Description

Solutions:
FIG. MINIMUM JUMPS TO REACH THE END LRU● INTERACTIVE
Visualize
def count_min_jumps(jumps):
@lru_cache(maxsize=None)
def recursion(i):
if i == n - 1:
return 0
else:
mini = sys.maxsize
for j in range(1, min(jumps[i] + 1, n - i)):
required = 1 + recursion(i + j)
mini = min(mini, required)
return mini
 
n = len(jumps)
return recursion(0)