Let’s use an example of a dynamic programming problem to illustrate the concept. I didn’t choose an easy example, since it would fit more in the 2D Dynamic Programming category.

I. Introduction

Problem Statement

You are given an array of \(n\) integers representing the coins in balloons 🎈 When you burst a balloon 💥, you gain coins 🪙 equal to the product of the coins in the balloon and the ones adjacent. If there are no adjacent balloons, we consider virtual balloon with a value of \(1\).

For a range of balloons from \(3, 1, 5\):

  • Bursting \(1\) first gives you \(3 \times 1 \times 5 = 15\) coins.
  • Bursting \(3\) first gives you \(1 \times 3 \times 1 = 1\) coins. (using left virtual balloon)
  • A possibility would be bursting \(1\), then \(5\), then \(3\), which gives you a total of \(3 \times 1 \times 5 + 3 \times 5 \times 1 + 1 \times 3 \times 1 = 33\) coins.

But that possibility wouldn’t be the solution as the goal is to maximize the total coins 💰 you can collect by bursting all the balloons.

Understanding the problem

We can visualize the problem as a tree of choices, where each node represents a state of the balloons and the edges represent the choices made by bursting a balloon.

The leaves of the tree represent the final states where all balloons have been burst.

graph LR
    classDef three fill:#ffb3b3,stroke:#333
    classDef five fill:#b3b3ff,stroke:#333
    classDef one fill:#ffffb3,stroke:#333
    classDef grey fill:#D3D3D3,stroke:#333

    A[3, 1, 5<br>Total Coins: 0]
    class A grey

    A --> B(<b>Burst 3</b><br>Total Coins: 0 + 1\*3\*1 = 3)
    class B three
    A --> C(<b>Burst 1</b><br>Total Coins: 0 + 3\*1\*5 = 15)
    class C one
    A --> D(<b>Burst 5</b><br>Total Coins: 0 + 1\*5\*1 =5)
    class D five

    B --> E(<b>Burst 1</b><br>Total Coins: 3 + 1\*1\*5 = 8)
    class E one
    B --> F(<b>Burst 5</b><br>Total Coins: 3 + 1\*5\*1 = 8)
    class F five

    C --> G(<b>Burst 3</b><br>Total Coins: 15 + 1\*3\*5 = 30)
    class G three
    C --> H(<b>Burst 5</b><br>Total Coins: 15 + 3\*5\*1 = 30)
    class H five

    D --> I(<b>Burst 3</b><br>Total Coins: 5 + 1\*3\*1 = 8)
    class I three
    D --> J(<b>Burst 1</b><br>Total Coins: 5 + 1\*3\*1 = 8)
    class J one

    E --> K(<b>Burst 5</b><br>Total Coins: 8 + 1\*5\*1 = 13)
    class K five
    F --> L(<b>Burst 1</b><br>Total Coins: 8 + 1\*1\*1 = 9)
    class L one
    G --> M(<b>Burst 5</b><br>Total Coins: 30 + 1\*5\*1 = 35)
    class M five
    H --> N(<b>Burst 3</b><br>Total Coins: 30 + 1\*3\*1 = 33)
    class N three
    I --> O(<b>Burst 1</b><br>Total Coins: 8 + 1\*1\*5 = 13)
    class O one
    J --> P(<b>Burst 3</b><br>Total Coins: 8 + 1\*3\*1 = 11)
    class P three

    K --> R(Total Coins: 13)
    class R grey
    L --> S(Total Coins: 9)
    class S grey
    M --> T(Total Coins: 35)
    class T grey
    N --> U(Total Coins: 33)
    class U grey
    O --> V(Total Coins: 13)
    class V grey
    P --> W(Total Coins: 11)
    class W grey

We want to be able to identify the optimal path through this tree that maximizes the coins collected. In here for example, we can see that the optimal path is to burst the balloons in the order of 1, 3, 5 which gives us a total of 35 coins.

But building this tree explicitly would be inefficient, especially for larger arrays of balloons. Instead, we can use dynamic programming to efficiently compute the maximum coins for any subarray of balloons.

II. Dynamic Programming Approach

How do we know it’s a dynamic programming problem?

The problem of bursting balloons can be classified as a dynamic programming problem due to the following characteristics:

  • Asking for optimization
    • Multiple valid possibilities
    • Only one is optimal (the one that maximizes the coins)
  • Sequential decision-making
    • There is choice to make at each step (which balloon to burst)
    • Future decisions depend on past choices (available balloons change)

A greedy solution is about choosing the best option at each step, without considering the overall problem. But here there’s no greedy choice that guarantees the optimal solution, as the order of bursting balloons matters.

Popping a balloon that gives the max coin first won’t always yield the best result. (In 3, 1, 5, 8, bursting 5 gives more coins at first but end up at 96 while bursting the 1 first will yield up to the optimal solution at 167 coins).

What is Dynamic Programming

We can solve this problem using dynamic programming, where the overall solution will be computed from the result for a larger problem using the results of its sub-problems.

For that we need to understand these concepts:

  • Base Case: The base case is the simplest, smallest instance of the problem that can be solved directly without recursion or iteration, serving as the foundation for building up the solution.

  • State: A state represents a unique configuration of the problem that encapsulates all the necessary information, to make decisions and compute results for every sub-problem which build up to include the final solution.

  • Transition formula: The transition defines the formula to build the solution of the current sub problem from the previous state. That solution is then stored in the state to calculate the next one.

We can implement this solution either iteratively (bottom up) or recursively (top down).

  • The iteration build up the state from the base case to the final solution applying the transition function at each step.
  • The recursion goes from the final solution down to the base case, applying the transition function recursively.

We usually store the state in an array that represent all the cases. We call it dp in an iterative solution, but in a recursive solution it is referred to as memo since we use it for memoization to avoid recomputing the same sub-problems on recursion.

Decomposing the problem

To identify the sub-problems in dynamic programming, we need to find a way to break down the original problem into smaller, self-contained pieces that can be solved independently. Solving those problems independently allows us to build up the optimal solution.

Sub-problems in a dynamic programming problem are often identified by what decisions can be made at each step

Here we want to calculate the maximum coins which depends on the neighbours of the balloon we burst, and so on until there’s no balloon.

With the [3, 1, 5] example, I represented each range we would get when popping a balloon. The virtual balloon at the beginning and end of the array will be represented as \((1)\) (as they don’t contribute to the coins).

We start with \(n + 2\) balloons (including the virtual ones, but we can only burst the actual ones).

graph TD
    B1["(1), 3, 5, (1)"] --> F1["(1), 5, (1)"]
    B1 --> E1["(1), 3, (1)"]
    D1["(1), 3, 1, (1)"] --> E1
    C1["(1), 1, 5, (1)"] --> F1
    D1 --> G1["(1), 1, (1)"]
    C1 --> G1
    A1["(1), 3, 1, 5, (1)"] --> B1
    A1 --> C1
    A1 --> D1

Looking at this tree we can draw some conclusions:

  • cases where it’s only \(1\) balloon left are simple to calculate, but not easy to reach
    • If there’s only one balloon left, the value gained is equal to the balloon’s value since virtual balloons are treated as \(1\).
    • But we don’t know the total coin since it depends on which balloons were burst before.
  • there are multiple paths leading to the same sub-problem.
    • Multiple arrows point to the same sub-problem \([5]\) or \([1]\) or \([3]\), indicating that different sequences of bursting balloons can lead to the same configuration.

The choice we have, is at any given time which balloon to burst last? Knowing that, we can either:

  • ask the same question again for the remaining range, until there’s just one balloon remaining. (Top-down approach)
  • calculate each maximum coins obtained for every increasing subset based on smaller ones’ maximum to get to the solution for the full range (Bottom-up approach)

III. Solving the problem

Setting up the base case

When there are no balloon to burst, the coins collected is obviously \(0\), those are trivial cases. The base case is when there’s only one balloon left to burst.

Considering a range \([i]\) in \(nums\) with \(i \in [1, \text{length}(\text{nums - 1})]\) (since we padded nums with the virtual balloons), there’s only one balloon \(nums[i]\) to burst. The coins collected can be calculated with:

\[coins = nums[i-1] \times nums[i] \times nums[i+1]\]

So for example in our [3, 1, 5] example, we use the virtual balloons at the edges:

  • Bursting 3 gives (1) * 3 * 1 = 3 coins.
  • Bursting 1 gives 3 * 1 * 5 = 15 coins.
  • Bursting 5 gives 1 * 5 * (1) = 5 coins.

That’s the base to calculate the next ranges.

Defining the state

For the state we care about storing the best outcome based on the popped balloons. We can pop them in any order from the start to the end or randomly. Since I want to try every combination, I also want to know which combination gives the best outcome.

So I will represent the state as a 2D array, where each cell dp[i][j] represents the maximum coins obtainable for that range. The maximum coin will be in dp[0][n-1] which represent the range with every balloon popped.

To find that out, we’ll be using the transition function, to use the maximum coins obtained when bursting a balloon last in a given range.

Formulating the transition function

Finding the transition function

We can formulate the sub-problems as follows:

For any range \([\textcolor{#E6B800}{i}, \textcolor{#E6B800}{j}]\) within \(nums\), we consider each balloon \(\textcolor{#FFA500}{k}\) between \(\textcolor{#E6B800}{i}\) and \(\textcolor{#E6B800}{j}\) as potentially the last one to burst:

  1. When \(\textcolor{#FFA500}{k}\) is the last balloon to burst:
    • Its adjacent balloons are the ones at the boundaries of the current range.
    • For the range \([i, j]\), the adjacent balloons are \(nums[i]\) and \(nums[j]\).
  2. Calculating the coins for the bursting balloon at index \(\textcolor{#FFA500}{k}\) in the range \([\textcolor{#E6B800}{i}, \textcolor{#E6B800}{j}]\):
    • The coins obtained are: \(nums[i] \times nums[k] \times nums[j]\)
    • If \(nums[i]\) or \(nums[j]\) are out of range, they are treated as \(1\) (virtual balloons).
  3. Total coins for the range \([\textcolor{#E6B800}{i}, \textcolor{#E6B800}{j}]\):
    • \(dp[i][k−1]\): is the maximum coins obtainable by bursting all the balloons in the range \([i, k-1]\) (the left subarray before \(k\)).
    • \(dp[k+1][j]\): is the maximum coins obtainable by bursting all the balloons in the range \([k+1, j]\) (the right subarray after \(k\)).

Now we can assemble that into our transition function, that can be used to fill the state \(dp\) for all sub-arrays of \(nums\), the padded balloon array:

\[dp[\textcolor{#E6B800}{i}][\textcolor{#E6B800}{j}] = \underset{i \lt k \lt j}{\max}(dp[\textcolor{#E6B800}{i}][\textcolor{#FFA500}{k}-1] + nums[\textcolor{#E6B800}{i}] \times nums[\textcolor{#FFA500}{k}] \times nums[\textcolor{#E6B800}{j}] + dp[\textcolor{#FFA500}{k}+1][\textcolor{#E6B800}{j}])\]

Example

The formula calculates the maximum coins for the range [i, j] by considering every possible balloon at index k as the last one to burst, adding the coins from bursting k last to the maximum coins from the left and right sub-arrays, and then taking the best (maximum) result.

We can now use this transition function to fill our DP table iteratively or recursively. For example, if we want to calculate the maximum coins for the range [3, 1, 5] if we were to consider the range [1, 5], meaning the state at dp[2][4] we would have:

// balloons with padded ones
const nums = [1, 3, 1, 5, 1]
// indexes    0  1  2  3  4
// Between index [1, 4] we have nums[2] = 1, nums[3] = 5 and nums[4] = 1
const subbarray = [1, 5, 1]

Here is the calculation for dp[2][4] for the range [1, 5, 1] and remember, we padded the initial balloon array with the virtual ones (hence the 1 after the 5):

\[\begin{aligned} dp[2][4] &= \max_{k=3} \left(dp[2][k-1] + nums[2] \times nums[k] \times nums[4] + dp[k+1][4]\right) \\ &= dp[2][3-1] + nums[2] \times nums[3] \times nums[4] + dp[3+1][4] \\ &= dp[2][2] + nums[2] \times nums[3] \times nums[4] + dp[4][4] \\ &= 0 + 1 \times 5 \times 1 + 0 \\ &= 5 \end{aligned}\]

For this range, there’s only one possible k which is 3, so it directly gives dp[2][4] = 5, with more k we would have taken the maximum of all the possible values.

Applying the transition

Applying the formula for all possible ranges of balloons will allow us to fill the DP table iteratively. We need to loop from smaller ranges (omitting the virtual balloons) to larger ranges as the transition depends on previously computed values.

The state for [3, 1, 5] would look like:

// State for (1) [3, 1, 5] (1)
// 3 elements, so we need a 5x5 table to account for all ranges including virtual boundaries
const dp = [
// 0  1  2  3   4  
  [0, 0, 3, 30, 35], // dp[0][3] = 30
  [0, 0, 0, 15, 30],
  [0, 0, 0, 0, 5],
  [0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0]
];

The dp table is filled based on the transition function, where each cell dp[i][j] represents the maximum coins obtainable by bursting all balloons in the range [i, j].

If we were to represent in a diagram with a bit more information:

graph TB
    classDef three fill:#ffb3b3,stroke:#333
    classDef five fill:#b3b3ff,stroke:#333
    classDef one fill:#ffffb3,stroke:#333
    classDef grey fill:#D3D3D3,stroke:#333
    classDef invalid fill:#D3D3D3,stroke:#333
    classDef noBalloons fill:#FFFFFF,stroke:#333

    subgraph "DP Matrix"
        A["dp[0][0]<br>No balloons"]:::noBalloons --> B["dp[0][1]<br>No balloons"]:::noBalloons
        B --> C["dp[0][2]<br>Burst 3<br>Coins: 3"]:::three
        C --> D["dp[0][3]<br>Burst 3, 1<br>Max Coins: 30"]
        D --> E["dp[0][4]<br>Burst 3, 1, 5<br>Max Coins: 35"]

        F["dp[1][0]<br>❌"]:::invalid --> G["dp[1][1]<br>No balloons"]:::noBalloons
        G --> H["dp[1][2]<br>No balloons"]:::noBalloons
        H --> I["dp[1][3]<br>Burst 1<br>Coins: 15"]:::one
        I --> J["dp[1][4]<br>Burst 1, 5<br>Max Coins: 30"]

        K["dp[2][0]<br>❌"]:::invalid --> L["dp[2][1]<br>❌"]:::invalid
        L --> M["dp[2][2]<br>No balloons"]:::noBalloons
        M --> N["dp[2][3]<br>No balloons"]:::noBalloons
        N --> O["dp[2][4]<br>Burst 5<br>Coins: 5"]:::five

        P["dp[3][0]<br>❌"]:::invalid --> Q["dp[3][1]<br>❌"]:::invalid
        Q --> R["dp[3][2]<br>❌"]:::invalid
        R --> S["dp[3][3]<br>No balloons"]:::noBalloons
        S --> T["dp[3][4]<br>No balloons"]:::noBalloons

        U["dp[4][0]<br>❌"]:::invalid --> V["dp[4][1]<br>❌"]:::invalid
        V --> W["dp[4][2]<br>❌"]:::invalid
        W --> X["dp[4][3]<br>❌"]:::invalid
        X --> Y["dp[4][4]<br>No balloons"]:::noBalloons
    end

There are two cases why we have 0 in the table:

  • When \(\textcolor{#E6B800}{i} > \textcolor{#E6B800}{j}\): Marked as “❌” in the table,
    • this means that this range is invalid since it starts after it ends.
  • When \(\textcolor{#E6B800}{i} = \textcolor{#E6B800}{j}\) or \(\textcolor{#E6B800}{i} + 1 = \textcolor{#E6B800}{j}\): Marked as No balloons in the table,
    • there’s no balloon \(\textcolor{#FFA500}{k}\) to burst in this range, so we cannot gain any coins.

The rest correspond at the maximum obtained when bursting the balloons in the range \([\textcolor{#E6B800}{i}, \textcolor{#E6B800}{j}]\). You can find that it matches the result we had found in the first diagram when calculating the maximum coins for each path through the tree.

IV. Implementation

Algorithm description

For the implementation, let’s list the step based on our above analysis:

  1. Add virtual balloons: Create a new array nums that includes 1 at both ends of the input array, filtering out any non-positive integers.
  2. Initialize the DP table: Create a 2D array dp of size n² initialized to 0.
  3. Iterate over subarray lengths: Loop through all possible subarray lengths from 2 to n.
    • below 2, there’s no balloon to burst in the subarray
  4. Iterate over starting indices: For each subarray length,
    • loop through all possible starting positions i for the subarray.
    • The ending index j is calculated as i + subarrayLength.
  5. Iterate over possible last balloons to burst: For each subarray [i,j],
    • loop through all possible indices k (where i < k < j) to consider as the last balloon to burst.
  6. Apply the transition function: Update dp[i][j] using the transition function based on previous states.
    • Calculate the coins obtained by bursting balloon k last, and add the maximum coins from the left and right sub-arrays.
    • Saving or updating the max with dp[i][j] = max(dp[i][j], dp[i][k] + nums[i] * nums[k] * nums[j] + dp[k][j])
    • This ensures that we consider all possible last balloons to burst in the current subarray and only keep the max possible value.
  7. Return the final result: The maximum coins obtainable by bursting all balloons is stored in dp[0][n-1].

Typescript example

Here’s the TypeScript implementation of the maxCoins function:

// Iterative solution
export function maxCoins(iNums: number[]): number {
  const nums: number[] = [1, ...iNums.filter(i => i > 0), 1];
  const n: number = nums.length;
  const dp: number[][] = Array(n).fill(null).map(() => Array(n).fill(0));

  for (let subarrayLength = 2; subarrayLength < n; subarrayLength++) {
    for (let i = 0; i < n - subarrayLength; i++) {
      const j = i + subarrayLength;
      for (let k = i + 1; k < j; k++) {
        dp[i][j] = Math.max(
          dp[i][j],
          dp[i][k] + nums[i] * nums[k] * nums[j] + dp[k][j]
        );
      }
    }
  }
  return dp[0][n - 1];
}
Recursive Solution 
export function maxCoins(iNums: number[]): number {
  const nums: number[] = [1, ...iNums.filter(i => i > 0), 1];
  const n: number = nums.length;
  const dp: number[][] = Array(n).fill(null).map(() => Array(n).fill(-1));

  function helper(i: number, j: number): number {
    if (i >= j - 1) return 0; // Base case: no balloons to burst
    if (dp[i][j] !== -1) return dp[i][j]; // Return cached result if available

    let maxCoins = 0;
    for (let k = i + 1; k < j; k++) {
      const coins = nums[i] * nums[k] * nums[j] + helper(i, k) + helper(k, j);
      maxCoins = Math.max(maxCoins, coins);
    }

    dp[i][j] = maxCoins; // Cache the result
    return maxCoins;
  }

  return helper(0, n - 1); // Solve for the entire range
}

The algorithm works by iterating through all possible arrays and calculating the maximum coins obtainable for each subarray using the transition function defined earlier.

Here is a visual representation of how the DP table is filled for the input array [3, 1, 5], I didn’t add the padded virtual balloons in the diagram, but they are implicitly considered in the DP table and the results represented here.

graph TB
    classDef subarray fill:#d3d3d3;
    classDef result fill:#fbecd1,stroke:#f7d099;

    A["nums = [1, 3, 1, 5, 1]"] --> B("subarray length = 2"):::subarray;
    B --> C{"i = 0, j = 2<br>balloons: [3]"}:::subarray;
    C --> D{"dp[0][2] = 3"}
    B --> E{"i = 1, j = 3<br>balloons: [1]"}:::subarray;
    E --> F{"dp[1][3] = 15"}
    B --> G{"i = 2, j = 4<br>balloons: [5]"}:::subarray;
    G --> H{"dp[2][4] = 5"}
    A --> I("subarray length = 3"):::subarray;
    I --> J{"i = 0, j = 3<br>balloons: [3, 1]"}:::subarray;
    J --> K{"dp[0][3] = 30"}
    I --> L{"i = 1, j = 4<br>balloons: [1, 5]"}:::subarray;
    L --> M{"dp[1][4] = 30"}
    A --> N("subarray length = 4"):::subarray;
    N --> O{"i = 0, j = 4<br>balloons: [3, 1, 5]"}:::subarray;
    O --> P{"dp[0][4] = 35"}
    P --> Q["Return 35"]:::result;

Now for how efficient our algorithm is, we have:

  • Time Complexity: \(O(n^3)\) where \(n\) is the number of balloons
    • Because there are \(3\) nested loops
  • Space Complexity: \(O(n^2)\) for the DP table
    • Because we store results for all sub-arrays in a \(2D\) array