Dynamic Programming vs Divide and Conquer

Hi there, I think one of the most difficult patterns in the algorithms section is Dynamic Programming (DP). Additionally, DP is similar to Divide and Conquer (DC), but what is the difference?

In this article, I'm gonna share with you:

1. What is Dynamic Programming
2. What is Divide and Conquer
3. What is the difference between them in the examples
4. Which one to choose
5. Share my best practices and some templates for them

Definitions

Divide and Conquer - Let's start with the simplest one. It is an algorithm pattern that recursively breaks down a problem into independent sub-problems. The results of all sub-problems are combined to solve the whole problem.

Tips:

1. Break down a problem
2. Solve each subproblem independently
3. Combine the solutions
4. No overlapping subproblems - each subproblem is solved only once

Dynamic Programming - is an algorithm pattern with an optimization. It also breaks down a problem but into overlapping sub-problems. They share work and can be solved once and reused. "Dynamic Programming" is essentially an optimization technique for "Divide and Conquer" when you have overlapping subproblems. It trades memory for time by storing and reusing solutions to avoid redundant computation.

Tips:

1. Break down a problem into smaller overlapping sub-problems
2. Solve each sub-problem once and store the result (Top-Down or Bottom-Up pattern)
3. Reuse stored solutions
4. Optimal substructure - optimal solution to the problem contains optimal solutions to sub-problems

Top-Down example

const memo = new Map();
const fibonachi = (n) => {
  if (n <= 1) {
    return n;
  }

  if (memo.has(n)) {
    return memo.get(n);
  }

  const result = fibonachi(n - 1) + fibonachi(n - 2);
  memo.set(n, result);

  return result;
};

Bottom-Up example

const fibonachi = n => {
    let a = 1;
    let b = 1;

    for (let i = 3; i <= n; i++) {
        const c = a + b;
        a = b;
        b = c;
    }

    return b;
};

Differences

Divide and Conquer

1. QuickSort
2. Left subarray [from, nextTo] and right subarray [nextFrom, to] are completely separate
3. Sorting the left subarray doesn't help with sorting the right subarray
4. No shared work between subproblems

QuickSort([1,5,3,2,4])
├── QuickSort([0,1])     ← Independent
└── QuickSort([2,3,4])   ← Independent
    ├── QuickSort([2])   ← Independent
    └── QuickSort([3,4]) ← Independent

Dynamic Programming

1. Fibonacci
2. fib(5) needs fib(4) and fib(3)
3. fib(4) also needs fib(3) and fib(2)
4. fib(3) is calculated twice - this is an overlap!

fib(5)
├── fib(4)
│   ├── fib(3) ← Calculated twice
│   └── fib(2)
└── fib(3)     ← Calculated twice
    ├── fib(2) ← Calculated multiple times
    └── fib(1)

Complexity

Time

• Divide and Conquer - usually O(n log n) for sorting algorithms
• Dynamic Programming - varies by problem, but often O(n²) or O(n³)

Space

• Divide and Conquer - minimal extra memory (usually O(log n) for recursion stack, but might be O(1) for in place solutions)
• Dynamic Programming - requires additional memory to store solutions (O(n) to O(n²) typically)

Divide and Conquer Best Practices & Template

1. IDENTIFY if it's a Divide and Conquer problem:

   • Can the problem be broken into smaller, independent subproblems?
   • Do the subproblems have the same structure as the original problem?
   • Can solutions to subproblems be combined to solve the original problem?
   • Keywords: "sort", "search", "merge", "conquer", "recursive structure"

2. DEFINE the divide step:

   • How do you break the problem into smaller subproblems?
   • What is the size of each subproblem?
   • Are the subproblems independent?

3. FIND the recurrence relation (solution for the each problem):

   • What is the base case (smallest subproblem)?
   • How do you solve each subproblem recursively?

4. COMBINE the solutions:

   • How do you merge solutions from subproblems?
   • What is the complexity of the combine step?

Basic Template:

1. Divide - break the problem into subproblems
2. Conquer - solve subproblems recursively
3. Combine - merge solutions from subproblems
4. Return result

Dynamic Programming Best Practices & Template

1. IDENTIFY if it's a DP problem:

   • What are we optimizing? (max/min/count/boolean)
   • Optimal substructure (optimal solution contains optimal solutions to subproblems)
   • Overlapping subproblems (same subproblems are solved multiple times)
   • Keywords: "maximum/minimum", "count ways", "longest/shortest", "can we reach", "match"

2. DEFINE the DP state:

   • What does dp[i] or dp[i][j] represent?
   • You should easily understand what it means

3. FIND the recurrence relation (solution for the each problem):

   • How does dp[i] relate to previous states?
   • What are the transitions between states?

4. DETERMINE base cases:

   • What are the simplest cases we can solve directly?

5. DECIDE the order of computation:

   • Bottom-up (tabulation) vs Top-down (memoization)
   • Ensure dependencies are computed before the current state

Basic Template:

1. Initialize DP structure dp[i] = optimal solution for the first i elements
2. Set base cases: dp[0], dp[1], etc.
3. Fill table with recurrence: dp[i] = f(dp[i-1], dp[i-2], ...)
4. Return answer: dp[n]

Common Patterns: Divide and Conquer

Pattern 1: Array/List Division
Examples: QuickSort, MergeSort, Binary Search
Strategy: Split array into halves or parts

Pattern 2: Tree Division
Examples: Binary Tree Traversal, Tree Height Calculation
Strategy: Process left and right subtrees separately

Pattern 3: Matrix Division
Examples: Strassen's Matrix Multiplication, Matrix Operations
Strategy: Split matrices into quadrants

Pattern 4: Geometric Division
Examples: Closest Pair of Points, Convex Hull
Strategy: Divide space into regions

Pattern 5: String Division
Examples: Palindrome Detection, Suffix Array Construction, Pattern Matching in Chunks
Strategy: Split strings into substrings or process character by character

IMPORTANT: Not all string problems are suitable for divide and conquer! Avoid problems with overlapping subproblems (like LCS, Edit Distance) as they are better solved with Dynamic Programming.

Common Patterns: Dynamic Programming

Pattern 1: Linear DP (1D)
Examples: Fibonacci, House Robber, Climbing Stairs
State: dp[i] depends on dp[i-1], dp[i-2], etc.

Pattern 2: Grid DP (2D)
Examples: Unique Paths, Minimum Path Sum, Edit Distance
State: dp[i][j] depends on dp[i-1][j], dp[i][j-1], dp[i-1][j-1]

Pattern 3: Interval DP
Examples: Matrix Chain Multiplication, Palindrome Partitioning
State: dp[i][j] represents the optimal solution for the interval [i, j]

Pattern 4: Knapsack DP
Examples: 0/1 Knapsack, Unbounded Knapsack, Coin Change
State: dp[i][w] represents the optimal solution using the first i items with a weight limit of w

Pattern 5: String DP
Examples: Longest Common Subsequence, Edit Distance, Regular Expression
State: dp[i][j] represents solution for first i chars of string1 and first j chars of string2

That's it, I hope it's helpful, have a nice day 😉