Data Structures and Algorithms. Dynamic Programming

6 min readJul 22, 2024

Hi and it’s nice to see you!

This’s the last topic in this short course of DSA, that’s the Dynamic Programming.

I keen on this algorithm. Some guys afraid and avoid it, but the only thing is that it isn’t as hard as you might think at the first glance.

The most classical example we can observe here is the Fibonacci sequence of integers. We’ve already discussed it in the one of the first articles.

Fibonacci sequence is the integer sequence, where adjacent elements follow the formula below:

Let me clarify, that this sequence starts with two initial values, that’re 0 and 1.

Each time we want to get a new value, it’ll be calculated as the sum of two previous integers.

def fibo(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    
    return fibo(n - 1) + fibo(n - 2)

Since there’re two recursive calls, it leads to TC: O(2^n), because at each call you have to calculate two results separately, that will generate two new results and so on.

There’re four steps (framework) you should be aware to construct a correct DP algorithm:

base case

As you might recall, recursive functions require to have at least one base case to exit from a recursive call, otherwise you’ll get call stack overflow.

state

The state holds a value of any type and according to this function, it has only one parameter, that changes over recursive calls as an result of previous calculations. This way, it’s the 1DP state example.

state transition (recurrence relation)

Recurrence relation is the hardest part to construct an algorithm, because it declares HOW does the state changes between independent calls. To be short, it’s the transition formula and in many cases it’s unique.

ability to store result of previous computations (memo)

If you run this algorithm for small integers, okay, it’ll be work fine.

But then try to run with 1000. Did you noticed the difference?

There’s a huge amount of calculations to find an answer. Let’s improve it with a manual cache (however, there’s a fancy and handy decorator in Python, such as @cache).

def fibo(n):
    cache = {} # cache contains mapping "n: value"
    
    def helper(n):
        if n in cache: # if you have already stored a value
            return cache[n] # immediately return to avoid unnecessary ops
        if n == 0:
            return 0
        if n == 1:
            return 1

        cache[n] = helper(n-1) + helper(n-2)

        return cache[n]

    return helper(n)

fibo(500) # ...
fibo(1000) # RecursionError: ...

This’s the example of a classical Top-Down Dynamic Programming, where an input is reduced to a simple base case (step-by-step) with applying the cache.

Despite that it works correctly, we still get a RecursionError. Is there any way to improve it again?

There’s an alternative to Top-Down DP, that is Bottom-Up approach.

An idea remains the same, but this time we’ll replace a recursion with iteration.

def fibo(n):
    dp = [0] * (n + 1) 
    dp[1] = 1 # define this base case before

    for i in range(2, n + 1):
        # extract sum for two consecutive integers
        # and put it as a result
        dp[i] = dp[i - 1] + dp[i - 2]

    return dp[n]

print(fibo(1000)) # Ends without a RecursionError

At this point you might say:

Why didn’t you show it before???

The reason is that recursive DP is MUCH (!) MORE (!!) easier to understand and implement, but unfortunately, it isn’t so fast, as iterative DP.

When to use DP?

a problem asks you about finding something extremum/optimal (min/max) — min/max cost of doing smth, min/max amount of equal characters (Longest Common Subsequence/Substring)
at each step you have an opportunity to include/drop/whatever… an element into a particular result — this way it affect your future decisions

322. Coin Change

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.
Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.
You may assume that you have an infinite number of each kind of coin.

Example 1:

Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

Let us follow the framework, that we discussed earlier:

base case:

What if we’re out of money? then it’s impossible to find such a combination.
What if a combination succeeds? Okay, it’s a valid one, so simply return 0

state

For each step, what we need to know in advance? Only amount of money. This way let us store this amount as the single parameter (1DP state).

recurrence relation

Let’s say you have money = 11, and suppose, we have only coins = [1].

How much coins you should change, to make amount?

Exactly 11.

How you can do this?

Simply extract previously computed result from a particular coin.

nextState = dp(prevAmount — coin)

Will this work, if we have more than one coin?

Of course it will. Remember, we draw a fibonacci chart decomposition above? The point remains the same one.

memo

Simple memoization can be done with @cache decorator.

Here is some code. The first one with recursion and the second with tabulation.

# Recursion approach
class Solution:
    def coinChange(self, coins: list[int], amount: int) -> int:
        @cache 
        def dp(i):
            if i == 0: return 0
            if i < 0: return float('inf')
            return min([dp(i - c) + 1 for c in coins])

        ans = dp(amount)

        return -1 if math.isinf(ans) else ans

# Tabulation approach
class Solution:
    def coinChange(self, coins: list[int], amount: int) -> int:
        dp = [float('inf')] * (amount + 1)
        dp[0] = 0

        for i in range(1, amount + 1):
            for c in coins:
                if i - c >= 0:
                    dp[i] = min(dp[i], dp[i - c] + 1)

        ans = dp[amount]

        return -1 if math.isinf(ans) else ans

Time Complexity: O(N*amount).

Space Complexity: O(amount).

The last thing, that I want to focus your attention on is that DP might accept more than one dimension. The more dimensions you have, the more complexity they add.

Here is some piece of code:

# recursive approach
def dp(prev, cur, amount):
    ...

# iterative approach
dp = [[[0 for _ in range(amount)] for _ in range(cur)] for _ in range(prev)]

for i in prev:
  for j in cur:
    for k in amount:
      ...