What Is Dynamic Programming?

Dynamic programming is a way of solving a problem by remembering the answers to subproblems you have already solved. It applies when the naive recursive solution computes the same subproblems many times over, and when the problem decomposes into subproblems whose answers can be combined.

Two conditions have to hold. The first is overlapping subproblems: the recursive calls must revisit the same inputs, otherwise memoisation buys nothing. The second is optimal substructure: the optimal answer to the whole problem must be composed from optimal answers to the subproblems. A shortest path has both, which is why Dijkstra and Bellman-Ford are dynamic programs in disguise.

def count_paths(rows, cols):
    table = [[0] * cols for _ in range(rows)]
    for r in range(rows):
        for c in range(cols):
            if r == 0 or c == 0:
                table[r][c] = 1
            else:
                table[r][c] = table[r - 1][c] + table[r][c - 1]
    return table[rows - 1][cols - 1]


print(count_paths(3, 4))
print(count_paths(2, 2))

The outputs are 10 and 2. The count of paths to a cell is the count to the cell above plus the count to the cell on the left, since every path must arrive from one of them.

The mechanism is that you define a state, here a cell, and a recurrence that expresses the answer for that state in terms of other states. Then you either fill a table in dependency order, which is tabulation, or you compute states on demand and cache them, which is memoisation.

The trade-off to name is that dynamic programming is never asymptotically better than a well written greedy or graph algorithm when one exists, so you should look for those first. The value it adds is turning an exponential recursive search into a polynomial one, and the cost is the table, which is quadratic in the number of states for many problems. A useful heuristic is to write the recursive solution first, count how many calls it makes, and see whether the answer looks like a power of the input size.

Write the recursive solution and add a dictionary that caches the answer for each position.

def count_paths(rows, cols):
    memo = {}

    def walk(r, c):
        if r == 0 or c == 0:
            return 1
        key = (r, c)
        if key not in memo:
            memo[key] = walk(r - 1, c) + walk(r, c - 1)
        return memo[key]

    return walk(rows - 1, cols - 1)


print(count_paths(3, 4))
print(count_paths(2, 2))

The outputs are 10 and 2, the same as the table version. The difference is not in the answer but in how the work is organised.

The mechanism is the memo dictionary. Each position is computed once and then reused, so the total number of distinct states is the number of grid cells, and each one is computed in constant time. Without the memo, the recursion would compute the same position exponentially many times because each path into it triggers a fresh computation.

The trade-off to name is that the memoised version only computes the states it actually reaches, while the table version computes all of them. On a grid where most of it is unreachable, memoisation is much cheaper. On a problem where every state is needed anyway, the two cost the same. Memoisation also has a recursion depth cost, and the dictionary lookups are slower than array indexing, which is why the bottom up table is usually the version to ship once the solution is understood.

Prefer memoisation when the recursive formulation is obvious but the state space is sparse, so that only a fraction of the possible states is ever reachable. A memoised depth first search explores exactly the states that matter, while a bottom up table fills every state whether it is needed or not. Shortest paths in a large sparse graph are the classic example: a grid or a state space with many unreachable combinations benefits enormously from computing states on demand.

Prefer tabulation when the state space is dense, when the number of states is small enough that the table fits comfortably in memory, or when the recursion depth would be a problem. The bottom up form has no recursion limit, uses an array rather than a dictionary, and is usually several times faster in practice because array indexing beats hashing and there is no call overhead.

There are also hybrid cases worth knowing. Some problems are naturally recursive with a branching factor of two but have a huge state space, and there a depth first search with a visited set, which is memoisation with an explicit stack, is the right tool. Others can be memoised first to get a correct answer quickly and then rewritten bottom up once you have confirmed the recurrence, which is a common and sensible way to work.

The trade-off to summarise is memory against flexibility. A bottom up table has a predictable, fixed footprint but always pays for the whole space, while memoisation has a variable footprint that depends on what is reached. For an interview, the strongest answer is to describe the recurrence, state which of the two you would implement and why, and mention that the complexities are the same even though the constants differ.