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·
4 Approaches
FIG. 509 FIBONACCI NUMBER LRU● INTERACTIVE
visualization loads as you reach it
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·
4 Approaches
FIG. 70 CLIMBING STAIRS LRU● INTERACTIVE
visualization loads as you reach it
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·
4 Approaches
FIG. 1137 N TH TRIBONACCI NUMBER LRU● INTERACTIVE
visualization loads as you reach it
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·

Given a stair with n steps, implement a method to count how many possible ways are there to reach the top of the staircase, given that, at every step you can either take 1 step, 2 steps, or 3 steps.

Example 1:

Number of stairs (n) : 3

Number of ways = 4

Explanation: Following are the four ways we can climb : {1, 1, 1}, {1, 2}, {2, 1}, {3}

Example 2:

Number of stairs (n) : 4

Number of ways = 7

Explanation: Following are the seven ways we can climb : {1, 1, 1, 1}, {1, 1, 2}, {1, 2, 1}, {2, 1, 1}, {2, 2}, {1, 3}, {3, 1}

4 Approaches
FIG. STAIRCASE LRU● INTERACTIVE
visualization loads as you reach it
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·

Given a number n, implement a method to count how many possible ways there are to express n as the sum of 1, 3, or 4.

Example 1:

n : 4

Number of ways = 4

Explanation: Following are the four ways we can express 'n' : {1, 1, 1, 1}, {1, 3}, {3, 1}, {4}

Example 2:

n : 5

Number of ways = 6

Explanation: Following are the six ways we can express 'n' : {1, 1, 1, 1, 1}, {1, 1, 3}, {1, 3, 1}, {3, 1, 1}, {1, 4}, {4, 1}

4 Approaches
FIG. NUMBER FACTORS LRU● INTERACTIVE
visualization loads as you reach it
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·
4 Approaches
FIG. 746 MIN COST CLIMBING STAIRS LRU● INTERACTIVE
visualization loads as you reach it
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·

Given a staircase with n steps and an array of n numbers representing the fee that you have to pay if you take the step. Implement a method to calculate the minimum fee required to reach the top of the staircase (beyond the top-most step). At every step, you have an option to take either 1 step, 2 steps, or 3 steps. You should assume that you are standing at the first step.

Example 1:

Number of stairs (n) : 6

Fee: {1, 2, 5, 2, 1, 2}

Output: 3

Explanation: Starting from index '0', we can reach the top through: 0->3->top The total fee we have to pay will be (1+2).

Example 2:

Number of stairs (n): 4

Fee: {2, 3, 4, 5}

Output: 5

Explanation: Starting from index '0', we can reach the top through: 0->1->top The total fee we have to pay will be (2+3).

4 Approaches
FIG. MINIMUM JUMPS WITH FEE LRU● INTERACTIVE
visualization loads as you reach it
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·
4 Approaches
FIG. 198 HOUSE ROBBER LRU● INTERACTIVE
visualization loads as you reach it
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·
FIG. 213 HOUSE ROBBER II TWO RANGES● INTERACTIVE
visualization loads as you reach it
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·

Given an array of positive numbers, where each element represents the max number of jumps that can be made forward from that element, write a program to find the minimum number of jumps needed to reach the end of the array (starting from the first element). If an element is 0, then we cannot move through that element.

Example 1:

Input = 4

Output = 3

Explanation: Starting from index '0', we can reach the last index through: 0->2->3->4

Example 2:

Input = 3

Output = 4

Explanation: Starting from index '0', we can reach the last index through: 0->1->2->3->8

3 Approaches
FIG. MINIMUM JUMPS TO REACH THE END LRU● INTERACTIVE
visualization loads as you reach it
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)