Dynamic Programming Concepts | Engineering Interview Kit

Concept

Dynamic Programming (DP) is arguably the most feared topic in algorithmic interviews.

At its core, Dynamic Programming is nothing more than Recursion + Memory.
It is a mathematical optimization technique. If a recursive algorithm calculates the exact same sub-problem multiple times, Dynamic Programming says: “Calculate it once, save the answer in a Hash Map/Array, and the next time you need it, just look it up instantly in $O(1)$ time.”

As George Santayana famously said: “Those who cannot remember the past are condemned to repeat it.”
Dynamic Programming is the act of remembering the past.

The Two Requirements

A problem can ONLY be solved with Dynamic Programming if it has these two specific mathematical properties:

Optimal Substructure: The optimal solution to the main problem can be constructed directly from the optimal solutions of its smaller sub-problems. (e.g., The shortest path from A to C is exactly equal to the shortest path from A to B + the shortest path from B to C).
Overlapping Subproblems: The recursive algorithm breaks the problem down into small sub-problems, and it asks to solve the exact same sub-problem multiple times. (This is the critical difference between DP and Divide & Conquer. Merge Sort breaks the problem down, but it never sorts the exact same sub-array twice, so Merge Sort is not DP).

The Classic Example: Fibonacci

The Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13...
Formula: fib(n) = fib(n-1) + fib(n-2)

The Naive Recursive Approach:

function fib(n: number): number {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

If we call fib(5), it calls fib(4) and fib(3).
fib(4) then calls fib(3) and fib(2).
Notice that fib(3) is being calculated twice!
As $N$ gets larger, this redundancy explodes exponentially. fib(50) will trigger over 1 quadrillion function calls, freezing your computer. The time complexity is an apocalyptic $O(2^N)$ .

Enter Dynamic Programming

We can optimize this $O(2^N)$ disaster down to $O(N)$ using DP.
There are two distinct ways to implement Dynamic Programming:

1. Top-Down (Memoization):
Keep the exact same recursive tree, but add a Cache (Hash Map). Before doing any math, check the Cache. If the answer is there, return it! If not, calculate it, and save it to the Cache before returning.

2. Bottom-Up (Tabulation):
Throw away recursion entirely. Start from the absolute bottom (n=0, n=1), put them in an Array, and build your way up to n=50 using a standard for loop.

Both approaches are considered valid DP. Tabulation is generally faster in hardware (no Call Stack overhead), while Memoization is generally easier for humans to conceptualize (you just write the naive recursion and slap a cache on it).

Interview Strategy

When you see a problem asking for the “Maximum”, “Minimum”, “Longest”, or “Total Number of Ways” to do something, your brain should immediately flag it as a potential DP problem.

The DP Framework:

Identify the State: What parameters change in the recursive function? (e.g., index, remainingWeight). This will be the key to your Cache.
Identify the Base Cases: What is the simplest, trivial scenario? (e.g., if (index < 0) return 0).
Write the Recurrence Relation: How does the current state mathematically rely on the previous states? (e.g., dp[i] = Math.max(dp[i-1], array[i] + dp[i-2])).

Interview Questions

Q: Is Backtracking the same thing as Dynamic Programming?
A: No. Backtracking (like generating all Permutations or solving Sudoku) generates every single valid combination. It does not cache the mathematical results of overlapping subproblems, because every single path is functionally unique. DP evaluates optimal combinations and throws away inferior paths by replacing them with a single cached integer.

Q: Can you use Dynamic Programming to find the longest path in a graph with cycles?
A: No! Dynamic Programming strictly requires an Acyclic dependency graph. If State A depends on State B, and State B loops back to depend on State A, you have an infinite circular dependency. The DP Cache will never resolve. DP is almost exclusively run on Arrays, Strings, Trees, and Directed Acyclic Graphs (DAGs).