Overview

Dynamic Programming (DP) is an optimization technique for problems that repeatedly solve the same smaller problems. Its central idea is simple: compute an answer once, save it, and reuse it. This can transform an impractically slow recursive solution into an efficient algorithm.

Key concepts

• Define a state that represents each subproblem
• Write a recurrence connecting states
• Set the base cases
• Store results with memoization or tabulation

What is Dynamic Programming?

DP applies when a problem has overlapping subproblems and optimal substructure. Rather than recomputing the same state, it stores the result in memory and retrieves it whenever that state appears again.

Why do we need Dynamic Programming?

Imagine counting the ways to climb 50 stairs when each move can cover one or two steps. A naive recursive solution recalculates the same smaller stair counts many times. DP remembers the answer for every step, avoiding that repeated work.

Key concepts

Overlapping Subproblems

The same smaller problem appears repeatedly. For example, a recursive Fibonacci calculation requests Fibonacci(3) through several branches. DP computes it once.

Optimal Substructure

An optimal solution can be assembled from optimal solutions to smaller subproblems. Shortest paths, knapsack variants, and many sequence problems have this property.

Dynamic Programming approaches

Memoization (Top-Down)

Memoization starts from the original problem, uses recursion to request smaller states, and caches each result when it is first computed.

function fibonacciMemo(n, memo = new Map()) {
  if (n < 2) return n;
  if (memo.has(n)) return memo.get(n);

  const result =
    fibonacciMemo(n - 1, memo) + fibonacciMemo(n - 2, memo);

  memo.set(n, result);
  return result;
}

console.log(fibonacciMemo(7)); // 13

Tabulation (Bottom-Up)

Tabulation starts with known base cases and uses loops to build progressively larger answers until it reaches the requested state.

function fibonacci(n) {
  if (n < 2) return n;

  const dp = [0, 1];

  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }

  return dp[n];
}

console.log(fibonacci(7)); // 13

Both approaches compute every necessary state once. Memoization can skip states that are never requested, while tabulation avoids recursive call-stack overhead.

Space optimization

If a recurrence depends only on a small number of previous states, the full table may be unnecessary. Fibonacci needs only the previous two values.

function fibonacciOptimized(n) {
  if (n < 2) return n;

  let previous = 0;
  let current = 1;

  for (let i = 2; i <= n; i++) {
    [previous, current] = [current, previous + current];
  }

  return current;
}

A practical DP workflow

• Define what the state means
• List the choices available from each state
• Write a recurrence for the answer
• Identify the smallest base cases
• Choose top-down or bottom-up evaluation
• Determine the required state order
• Analyze time and space
• Optimize memory only after correctness is clear

When should you use DP?

• The same subproblems appear repeatedly
• The answer can be built from smaller answers
• The problem asks for a count, minimum, maximum, or feasibility result
• Brute force branches into many repeated states
• Input constraints require a more efficient solution

Not every recursive or optimization problem is DP. If states do not overlap, divide and conquer may be a better description. If local choices can be proved optimal, a greedy solution may be simpler.

Common Dynamic Programming problems

• Fibonacci Sequence
• Climbing Stairs
• Coin Change
• Longest Common Subsequence
• Longest Increasing Subsequence
• 0/1 Knapsack
• Edit Distance
• Matrix Chain Multiplication

Time complexity improvement

A general DP running time is often the number of distinct states multiplied by the work needed to process each state.

Dynamic Programming vs Greedy

Advantages of Dynamic Programming

• Eliminates repeated calculations
• Can dramatically improve running time
• Produces optimal results for suitable problems
• Handles complex optimization and counting tasks
• Offers systematic top-down and bottom-up designs

Limitations of Dynamic Programming

• Recognizing the correct state can be difficult
• Tables and caches consume additional memory
• State transitions can be hard to derive
• Large state spaces may remain too expensive
• DP is unsuitable when subproblems do not overlap

Real-life applications

• Route optimization
• Resource allocation
• Financial planning
• DNA sequence alignment
• Text comparison
• Robotics
• Artificial Intelligence
• Game development

Tips for beginners

• Understand recursion first
• Write the brute-force recurrence
• Mark which calls repeat
• Begin with memoization
• Convert to tabulation after understanding dependencies
• Practice Fibonacci and Climbing Stairs before multidimensional DP

Key takeaways

• DP stores and reuses subproblem answers
• It requires overlapping subproblems and optimal substructure
• Memoization is top-down
• Tabulation is bottom-up
• DP can reduce exponential work to polynomial time
• The key design tasks are choosing state, recurrence, base cases, and evaluation order
• Memory can often be optimized after the solution is correct