Complete Dynamic Programming | Dynamic Programming Part 2

Every programmer reaches a point where basic recursion is no longer enough because it takes too much time. When a problem contains overlapping sub-problems and optimal substructure, simple brute-force solutions become very slow. This is where learning Advanced Dynamic Programming becomes important. 

It helps you move from repeated calculations to smart state design and better memory management. With the right DP approach, you can solve difficult problems more efficiently and improve your problem-solving skills.

What Are the Principles of Advanced Dynamic Programming?

To solve advanced algorithm problems, you often need more than simple one-dimensional arrays. Many complex DP problems require multi-dimensional state spaces because a single variable cannot store all the information needed to solve the problem. A state represents a specific sub-solution or situation inside a problem.

In advanced Dynamic Programming problems, a state may need to track multiple values at the same time, such as:

• Current index

• Remaining capacity

• Number of operations left

• Selected items

• Visited positions

The better you understand state design, the easier it becomes to solve advanced DP problems.

How Do Multi-Dimensional States Work in Advanced Dynamic Programming?

When solving Dynamic Programming problems, defining the correct state is one of the most important steps.

In simple problems such as finding the Fibonacci number, the state depends on only one variable.

However, advanced problems often need multiple variables because the answer depends on several conditions.

Multi-Parameter Representation

A state can contain two, three, or even more variables. For example, a state may look like:

DP[i][j]

or

DP[i][j][k]

Each dimension stores information about a different part of the problem. This allows the algorithm to keep track of more complex situations while solving subproblems.

Resource Tracking

Extra dimensions are often used to track limited resources. These resources may include:

• Available budget

• Remaining capacity

• Number of transactions

• Weight limits

• Energy points

By storing these values inside the state, the algorithm can make better decisions while building the final solution.

Directional States

In grid-based Dynamic Programming problems, extra dimensions can also track movement direction. This helps the algorithm know where it came from and where it can move next. Using directional states prevents invalid moves and avoids unnecessary calculations.

How Do DAGs Help in Advanced Dynamic Programming?

Every Dynamic Programming problem can be represented as a Directed Acyclic Graph (DAG). A DAG provides a simple way to understand how different states depend on each other.

Vertices as States

Each unique state or subproblem becomes a vertex in the graph. Every vertex stores information about a specific situation that needs to be solved. These states work together to build the final answer.

Edges as Dependencies

The edges between vertices represent dependencies. If there is an edge from State A to State B, it means State B needs the result of State A before it can be calculated. These connections show how information flows through the Dynamic Programming solution.

Why Must a DAG Be Acyclic?

A DAG must not contain cycles. If a cycle exists, one state will eventually depend on itself through a chain of other states. This creates an endless loop of dependencies. As a result, the algorithm cannot determine the correct order for solving subproblems. For this reason, Dynamic Programming relies on an acyclic structure so that every state can be calculated successfully and used by future states.

Important Optimization Techniques in Advanced Dynamic Programming

Writing a functional recurrence relation is a great first step, but raw relations often suffer from high time and space complexities. Optimization techniques allow programmers to reduce computational overhead dramatically.

       [ Naive Recursive Approach ]
                    │
                    ▼ (Identify Overlapping Sub-problems)
      [ Top-Down Memoisation / Bottom-Up Tabulation ]
                    │
                    ▼ (Reduce Array Dimensions)
      [ Space-Optimised Sliding Window State ]

Space Optimization Using Rolling Arrays

Many dynamic programming algorithms rely only on the results of the immediate previous rows or columns. Instead of allocating a massive multi-dimensional matrix that consumes excessive memory, you can optimize space by recycling rows.

• Two-Row Buffering: If the state DP[i][j] only depends on values from DP[i-1], you only need two rows: one for the current step and one for the previous step.

• Modulo Indexing: Using the bitwise or arithmetic modulo operation (like i % 2) allows you to alternate between the two allocated rows, dropping space complexity by an entire factor of N.

• In-Place Updates: In specific problems like the classic 0/1 Knapsack, iterating backward through a single-dimensional array allows you to update values in-place without overwriting data needed for the current iteration.

State Reduction and Bitmasking

When choices involve tracking a collection of visited elements or subsets, explicit Boolean arrays become too heavy. Bitmasking serves as an excellent optimization technique here.

• Integers as Sets: A single 32-bit or 64-bit integer can represent a set of up to 64 items, where the ith bit is set to 1 if the item is included, and 0 otherwise.

• Fast Transitions: Bitwise operations like AND (&), OR (|), and shifts (<<, >>) complete in O(1) time at the hardware level, speeding up state evaluation.

• Exponential to Polynomial Shifts: While bitmask DP still scales exponentially based on the subset size, it drastically compresses the constant factor and memory footprint compared to tracking object states manually.

Memoisation vs Tabulation in Advanced Dynamic Programming

Choosing between the two primary implementation strategies depends heavily on the nature of the problem, recursion depth, and the specific distribution of states that need evaluation.

Classic Grid Problems in Advanced Dynamic Programming

Grid-based challenges are excellent for visualizing how multi-dimensional states evolve. Let us look at a foundational grid problem: maximizing collected resources while navigating a matrix.

The Apple Collection Problem

Consider an N x M grid where each cell contains a specific number of apples. You start at the top-left corner (0,0) and can only move down or right at any given step. The objective is to find the maximum number of apples you can collect by the time you reach the bottom-right corner (N-1, M-1).

Formulating the State and Base Case

Let DP[i][j] represent the maximum number of apples collected when reaching cell (i, j).

• Base Case: At the starting position, the maximum apples collected is simply the value of that initial cell.

• DP[0][0] = Grid[0][0]

• Boundary Conditions: For cells in the first row (i = 0), you can only arrive from the left cell. For cells in the first column (j = 0), you can only arrive from the top cell.

The Transition Formula

For any general cell (i, j), you can reach it either from the cell directly above it (i-1, j) or from the cell directly to its left (i, j-1). To maximize the yield, you pick the best path:

$$\text{DP}[i][j] = \text{Grid}[i][j] + \max(\text{DP}[i-1][j], \text{DP}[i][j-1])$$

Iterative Grid Implementation

Below is a clear, systematic implementation of this grid traversal logic using an iterative tabular format.

C++

// Tabular implementation for maximizing apple collection in a grid
#include <iostream>
#include <vector>
#include <algorithm>

int getMaximumApples(const std::vector<std::vector<int>>& grid) {
    int n = grid.size();
    int m = grid[0].size();
   
    // Create a 2D table initialized to 0
    std::vector<std::vector<int>> dp(n, std::vector<int>(m, 0));
   
    // Initialize the base case
    dp[0][0] = grid[0][0];
   
    // Fill out the first column
    for (int i = 1; i < n; ++i) {
        dp[i][0] = dp[i-1][0] + grid[i][0];
    }
   
    // Fill out the first row
    for (int j = 1; j < m; ++j) {
        dp[0][j] = dp[0][j-1] + grid[0][j];
    }
   
    // Fill the rest of the DP table
    for (int i = 1; i < n; ++i) {
        for (int j = 1; j < m; ++j) {
            dp[i][j] = grid[i][j] + std::max(dp[i-1][j], dp[i][j-1]);
        }
    }
   
    // Return the value at the target destination
    return dp[n-1][m-1];
}

Advanced Dynamic Programming Algorithms for Graph Transitions

Graph problems often require tracking paths, vertex choices, and weights. Combining shortest-path structures with dynamic programming allows you to solve network and routing problems efficiently.

Shortest Path with DP

Finding the shortest path in a Directed Acyclic Graph (DAG) can be framed cleanly as a DP problem. If we have an undirected graph with positive weights, we can construct shortest paths by defining clear directional states from a starting vertex.

Let DP[u] represent the shortest distance from the source vertex to vertex u.

The transition updates the destination state whenever a shorter path is discovered:

$$\text{DP}[u] = \min_{(v, u) \in \text{Edges}} (\text{DP}[v] + \text{Weight}(v, u))$$

Sequential Coin Customisation Update

Another fascinating variant involves updating states iteratively as new options or constraints are introduced. Consider a scenario where you want to construct a target sum S using a list of N coins with specific values.

Instead of processing values sequentially by sum, you can process them coin by coin. This variant updates the global array whenever a more optimal path or fewer coins are needed to reach a specific target state.

1. Set the base target DP[0] = 0 and initialize all other sum states to infinity.

2. Pick the first coin. Iterate through all possible sums from the coin's value up to S.

3. If adding the current coin to a previously solved smaller sum yields a lower coin count than the current value stored at that sum, update it immediately.

4. Repeat the entire cycle for the next coin. This ensures that every coin choice modifies the existing state matrix incrementally, optimizing both space and code complexity.

Structural Workflow for Solving Advanced Dynamic Programming Problems

Approaching a highly advanced question without a structured plan leads to messy code and logical errors. Follow this step-by-step workflow to approach any complex challenge systematically:

• Step 1: Identify the DP Properties – Verify if the problem can be broken down into smaller, recurring sub-problems (overlapping sub-problems) and check if an optimal solution to the large problem contains optimal solutions to its sub-parts (optimal substructure).

• Step 2: Define the State Clearly – Determine the minimal set of parameters that uniquely identify a sub-problem configuration.

• Step 3: Establish the Recurrence Relation – Write out the exact mathematical or logical link that updates a current state based on previously evaluated states.

• Step 4: Pinpoint Base Cases and Boundaries – Identify the smallest possible sub-problems where the answers are obvious or given implicitly.

• Step 5: Choose an Implementation Strategy – Use top-down memoisation if only a few states are reachable, or use bottom-up tabulation to avoid recursion overhead and open the door for space optimization.

• Step 6: Apply Memory Reductions – Inspect the transition lines. If the current calculation only requires the immediate last row or step, compress the multi-dimensional structure into a rolling array format.