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 Approachesclick to switch
Explanation

The recurrence is the classic fib(i) = fib(i - 1) + fib(i - 2) with base cases fib(0) = 0 and fib(1) = 1. Here we write the bare top-down recursion and let @lru_cache memoize every call automatically, so each subproblem is computed once. This keeps the code as close to the mathematical definition as possible.

Analysis
Time
O(n)
  • With memoization each of the n subproblems is solved exactly once.
Space
O(n)
  • The cache plus the recursion stack hold up to n entries.
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 Approachesclick to switch
Explanation

The number of ways to reach step i is ways(i) = ways(i - 1) + ways(i - 2), the same shape as Fibonacci, with base cases handled by i <= 2. We write the bare recursion and let @lru_cache memoize each subproblem automatically so it is only solved once.

Analysis
Time
O(n)
  • Each of the n subproblems is computed once thanks to the cache.
Space
O(n)
  • The cache plus recursion stack hold up to n entries.
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 Approachesclick to switch
Explanation

The Tribonacci recurrence sums the previous three values: trib(i) = trib(i - 1) + trib(i - 2) + trib(i - 3), with trib(0) = 0 and trib(1) = trib(2) = 1. We write the bare recursion and let @lru_cache memoize each subproblem automatically.

Analysis
Time
O(n)
  • Each of the n subproblems is solved once with caching.
Space
O(n)
  • The cache plus recursion stack hold up to n entries.
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 Approachesclick to switch
Explanation

Reaching step i from one, two, or three steps below gives ways(i) = ways(i - 1) + ways(i - 2) + ways(i - 3), with base cases i <= 1 and i == 2. We write the bare recursion and let @lru_cache memoize each subproblem automatically.

Analysis
Time
O(n)
  • Each of the n subproblems is solved once with caching.
Space
O(n)
  • The cache plus recursion stack hold up to n entries.
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 Approachesclick to switch
Explanation

Each expression ends in a 1, 3, or 4, so ways(i) = ways(i - 1) + ways(i - 3) + ways(i - 4), with base cases handled by i <= 2 and i == 3. We write the bare recursion and let @lru_cache memoize each subproblem automatically.

Analysis
Time
O(n)
  • Each of the n subproblems is solved once with caching.
Space
O(n)
  • The cache plus recursion stack hold up to n entries.
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 Approachesclick to switch
Explanation

To reach step i we either come from i - 1 paying cost[i - 1] or from i - 2 paying cost[i - 2], so f(i) = min(cost[i - 1] + f(i - 1), cost[i - 2] + f(i - 2)), with f(i) = 0 for i <= 1. We write the bare recursion and let @lru_cache memoize each subproblem automatically.

Analysis
Time
O(n)
  • Each of the n subproblems is solved once with caching.
Space
O(n)
  • The cache plus recursion stack hold up to n entries.
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 Approachesclick to switch
Explanation

Reaching step i costs the fee of the step we jumped from plus the best cost to that step: f(i) = min(fee[i - 1] + f(i - 1), fee[i - 2] + f(i - 2), fee[i - 3] + f(i - 3)), with the base case folded into i <= 3. We write the bare recursion and let @lru_cache memoize each subproblem automatically.

Analysis
Time
O(n)
  • Each of the n subproblems is solved once with caching.
Space
O(n)
  • The cache plus recursion stack hold up to n entries.
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 Approachesclick to switch
Explanation

At house i we either rob it (taking nums[i] plus the best from i - 2) or skip it (taking the best from i - 1), giving f(i) = max(nums[i] + f(i - 2), f(i - 1)), with f(i) = 0 for i < 0. We write the bare recursion and let @lru_cache memoize each subproblem automatically.

Analysis
Time
O(n)
  • Each of the n subproblems is solved once with caching.
Space
O(n)
  • The cache plus recursion stack hold up to n entries.
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·
Explanation

The houses are in a circle, so the first and last cannot both be robbed. We split into two linear sub-problems - rob houses nums[1:] (skip the first) or rob houses nums[:-1] (skip the last) - and take the larger. Here rob_simple() is the same function as rob() in the simple version of this problem (198. House Robber).

Analysis
Time
O(n)
  • Two linear passes over the houses, each O(n).
Space
O(n)
  • Slicing creates two arrays of size up to n, plus the dp used inside rob_simple().
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 Approachesclick to switch
Explanation

Unlike the earlier problems this builds forward from index 0: from i we try every reachable i + j and take f(i) = 1 + min over j of f(i + j), with f(n - 1) = 0 at the end. We write the bare recursion and let @lru_cache memoize each subproblem automatically.

Analysis
Time
O(n^2)
  • Each of the n states scans up to its jump range, so in the worst case the work is quadratic.
Space
O(n)
  • The cache plus recursion stack hold up to n entries.
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)