Algorithms - Dynamic programming - Optimization with overlapping subproblems

Published Mar 6, 2026

Posted in
programming
.net
c#
question

Intro

At the moment I am looking for a job, so I was forced to enter the world of technical interviews and the weird places like Hackerrank and Leetcode. They absolutely suck, but they have some interesting problems that generations of developers have tried to solve. In my mind there are two kinds of problems: the ones that can be solved with a little thinking and the ones that require some sort of a priori computer science knowledge. Since I have not had a formal software development education and since no matter how many jobs I've had, they always ask me about algorithms, but then I never have to use them, the ones requiring such esoterics always scare me.

Compounding this is the fact that documentation about such concepts is made for people in computer science courses by people teaching computer science courses, which are usually some kind of math people at heart. 90% of the effort of understanding any of that is reading through their obtuse formalizations. So I've decided I would help myself and other fellow programmers understand these concepts in a way that can be understood.

In my research into these coding test platforms, the problems that cannot be solved with just a little thinking and some loops are 80% covered by just 8 categories of problems:

Optimization with overlapping subproblems (coin change, longest increasing subsequence, knapsack variants, matrix chain) - solved with Dynamic Programming (memoization/tabulation).
Pathfinding, connectivity, or level-order processing in grids/graphs (number of islands, shortest path in maze, rotten oranges) - solved with Graph Traversal: BFS and DFS.
Hierarchical data processing (tree diameter, in order traversal, BST validation, lowest common ancestor) - solved with Tree Traversals and Properties (pre/in/post-order, level-order, recursion/DFS on trees).
Exhaustive search with pruning (permutations, subsets, N-Queens, sudoku solver, word search) - solved with Backtracking.
Local optimal choices that work globally (jump game, task scheduler, fractional knapsack) - solved by Greedy Algorithms.
Efficient "top-k" or priority processing (merge k sorted lists, kth largest element, task scheduler with cooldown) - solved with Heaps / Priority Queues.
Efficient union of sets / cycle detection in graphs (redundant connection, number of provinces, Kruskal's MST) - solved with Union-Find (Disjoint Set Union) with path compression & union-by-rank.
Searching in sorted/monotonic spaces (search in rotated sorted array, minimum in rotated array, binary search on answer for capacity problems) - solved by Binary Search (advanced variants).

Bonus:

Efficient prefix and pattern matching - solved by Trie and KMP String Search
Efficient range queries and updates - solved by Segment Tree and Fenwick Tree
Shortest paths with negative weights and all-pairs - solved by Bellman-Ford and Floyd-Warshall

Today I will be covering Dynamic Programming (DP), which solves optimizations with overlapping subproblems. And no, I will not be making crass jokes about the abbreviation.

When to use Dynamic Programming

Recognize a problem that can be solved with DP by these signs:

it is too slow to solve with brute force
the solution for the problem can be built from best solutions to subproblems
the same subproblems (yielding the same result) need solving multiple times

Example - Fibonacci

The poster problem for this category is Fibonacci numbers. It's funny, but when I first learned about this series of numbers I was in school, and I knew more math than programming. When you start with the mathematical definition of the Fibonacci function, the naive computer implementation is terrible, so learning Dynamic Programming with this seems reasonable. But after decades away from school, when presented with the problem, the implementation cannot be more different.

Here is the general definition: a function F(x) which for 0 and 1 returns a defined number, then for any other x, it is computed as F(x-1)+F(x-2). Let's write this in C#, just so you see how silly it is:

int F(int x)
{
    if (x == 0) return 0;
    if (x == 1) return 1;
    return F(x - 1) + F(x - 2);
}

Readable, functional, faithful to the mathematical function, but completely inefficient. Let's add a counter to see how many times this function gets executed:

(int result,int count) F(int x)
{
    if (x == 0) return (0,1);
    if (x == 1) return (1,1);
    var (r1, c1) = F(x - 1);
    var (r2, c2) = F(x - 2);
    return (r1+r2, c1 + c2);
}

// F(10) returns (55, 89)
// F(20) returns (6765, 10946)
// F(30) returns (832040, 1346269)

Now let's think about the problem as a software developer. The client needs the last value of a series of numbers that start with 0, 1, and then add the last two numbers in the series to get the next one. It's an iteration function. The result, when you think about it in these terms, becomes obvious:

// loop solution
(int result, int count) F(int x)
{
    if (x == 0) return (0, 1);
    if (x == 1) return (1, 1);
    var (x1,x2) = (0,1);
    var c = 1;
    for (int i = 2; i <= x; i++)
    {
        (x1,x2) = (x2, x1 + x2);
        c++;
    }
    return (x2, c);
}

// F(30) returns (832040, 30)

So we optimized a function to run 30 times instead of 1.35 million times. Quite an improvement, and all it took was thinking like a software engineer, not like a math geek. This type of solution is called "bottom up dynamic programming" or "tabulation" and is usually the most efficient one. However, there is another solution called "top-down dynamic programming" or "memoization" which is what some computer science guys expect. Let's take a look:

var memo = new Dictionary<int, int>();

int F(int n)
{
    if (n <= 1) return n;
    if (memo.ContainsKey(n)) return memo[n];

    memo[n] = F(n - 1) + F(n - 2);
    return memo[n];
}

Here we used the naive structure of the code, preserving the math semantics, but cached the results of the function for known values. This is actually the kind of stuff they expect from you, even if it's clearly less efficient! Because that's what they teach in school as an example. It's the printing of "hello, world!" and the unit test for a calculator class that only knows how to add two numbers all over again.

Yet, there is a very good reason to use memoization sometimes and that is if you plan to run the function multiple times using the same dictionary. You are basically constructing a table of key/value pairs and using that to cache the results. An even more efficient implementation - in this case - is using a `List<int>` rather than a dictionary, since the keys are sequential integers. Since you know you are going to need all values from 0 to n to calculate F(n), then you can already create/expand the list to have N items.

They will also ask about complexity or the "Big O notation". If you don't know what that is, it's a fancy notation for describing the magnitude of time and space used by the algorithm. The naive implementation is O(Fibonacci(n+1)) in time, which is funny, as it describes the complexity with the function you're supposed to implement. The tabulation and the memoization versions are O(n) in time, or "linear", the complexity increases linearly with n. The space complexity is theoretically O(1) or "constant" for the naive and the tabulation version, while the memo version is O(n) because we store all n values in the dictionary with n keys..

I said theoretically, because practically, for the naive and memo versions, there is also extra overhead because of the recursive nature of the implementation. The data for each execution will be stored in the stack, which adds another O(n) in space and is also limited in size. Learn about Stack vs. Heap in programming and well as the Big O notation separately, if you want to drill down.

Theory

The definition sounds like this: Dynamic programming usually refers to simplifying a decision by breaking it down into a sequence of decision steps over time.

Two ways to do it:

Top-down + Memoization - Start from the big problem, recurse down, but cache results in a dictionary/array so each unique subproblem is solved only once.
Bottom-up + Tabulation - Start from the smallest subproblems, build a table iteratively up to the full problem. Usually uses less stack and is faster in practice.

The memoization approach is often easier and more natural, but every problem that can be solved with memoization can usually be solved with tabulation as well. If a problem has a correct recursive formulation with overlapping subproblems, you can always rewrite it as an iterative bottom-up solution by carefully filling a table (or multiple tables) in the right dependency order. The vast majority of DP problems taught and asked in interviews (Fibonacci, knapsack, coin change, longest common subsequence (LCS), edit distance, matrix chain multiplication, longest increasing subsequence, house robber, word break, regex matching, etc.) have clean bottom-up solutions.

Common Pitfalls & Trade-Offs

Initialize dp correctly! (Often dp[0]=0 or 1, others int.MaxValue or -1)
Watch for off-by-one (array size amount+1)
Memo dict vs array: array/list is faster and uses less memory for integer keys 0..N
Space: top-down can use O(N) stack + O(N) memo; bottom-up usually just O(N)
When amount N is huge (>10⁵ - 10⁶), DP might not fit - look for math or greedy instead

Example - Coin change (minimum coins)

Let's take another example, the exact change coin problem.

Problem: Given coins[] of different denominations and int amount, return the fewest coins needed to make exactly amount. Infinite supply of each coin. If impossible, return -1.

The memoization solution comes easier, because it's an iterative fix of the naive implementation:

Dictionary<int, List<int>?> memo = []; // memo: Memoization dictionary to store results for subproblems

IList<int> CoinChange(int[] coins, int amount)
{
    var result = FindMinCoins(coins, amount);
    return result ?? [];
}

List<int>? FindMinCoins(int[] coins, int remaining)
{
    if (remaining == 0)
        return [];

    if (remaining < 0)
        return null;

    if (memo.ContainsKey(remaining)) // memo: Check if the result for this amount is already computed
        return memo[remaining];

    List<int>? best = null;

    foreach (var coin in coins)
    {
        var subResult = FindMinCoins(coins, remaining - coin);
        if (subResult != null)
        {
            var candidate = new List<int>(subResult) { coin };
            if (best == null || candidate.Count < best.Count)
            {
                best = candidate;
            }
        }
    }

    memo[remaining] = best; // memo: Store the computed result in the memoization dictionary
    return best;
}

var result = CoinChange([1, 5, 10, 25], 30);
Console.WriteLine("["+string.Join(", ", result)+"]"); // returns [25, 5]

The lines with "memo:" comments are the difference between the naive and memoized versions.

So what did we do here? We started with the total amount of money and tried every single coin. Once a coin is used, the amount decreases with the value of the coin. If the amount if negative, we overspent and return null for an unusable solution. If the amount is 0, then we return an empty array and stop the recursive processing. If the amount is larger than zero, we now have to solve the exact same problem, but with a smaller amount.

Let's see the tabulation solution.

IList<int> CoinChange(int[] coins, int amount)
{
    if (amount == 0) return [];

    var dp = new int[amount + 1];     // dp[i] will hold the minimum number of coins needed for amount i
    var prev = new int[amount + 1];   // to reconstruct the solution

    Array.Fill(dp, int.MaxValue);
    dp[0] = 0;

    for (var i = 1; i <= amount; i++)
    {
        foreach (var coin in coins)
        {
            if (i >= coin && dp[i - coin] != int.MaxValue)
            {
                var candidate = dp[i - coin] + 1;
                if (candidate < dp[i])
                {
                    dp[i] = candidate;
                    prev[i] = coin;          // remember which coin we used
                }
            }
        }
    }

    if (dp[amount] == int.MaxValue)
        return [];          // impossible

    // Reconstruct the list of coins
    List<int> result = [];
    var current = amount;

    while (current > 0)
    {
        var coin = prev[current];
        result.Add(coin);
        current -= coin;
    }

    return result;
}

var result = CoinChange([1, 5, 10, 25], 30);
Console.WriteLine("["+string.Join(", ", result)+"]"); // returns [25, 5]

A lot more daunting, but simple once you "get it":

We store everything in arrays, where the index is the amount. I guess one could use dictionaries instead, but for small amounts - like the ones used in interview questions - the size of the array is less important than the efficiency of execution of the index in a static array.
We fill the array with int.MaxValue, so that any other value is preferable
We use the prev array to store the coin we last used for every calculation - smart solution to allow us to reconstruct the list of coins
when we just calculate and store the number of coins for each amount up to the desired amount.

It's just like the Fibonacci thing, only more complicated.

Conclusion

Use Dynamic Programming when a problem can be split into smaller pieces that get executed multiple times, yielding the same result each time. The top down approach is more intuitive, but the bottom up approach is usually more efficient.