Overlapping subproblems: memoisation vs tabulation; counting calls

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

• Coins {1, 3, 4}, amount 6: greedy coins vs optimal? from Lesson 4.2.4
• T(n) = T(n − 1) + T(n − 2)? from Lesson 1.2.4
• Huffman cost equals? from Lesson 4.2.3

1 · The Hook

🎣

The naive recursive Fibonacci function recomputes fib(3) again and again: fib(30) makes over a million calls to compute a number from 31 distinct subproblems. Dynamic programming (DP) computes each subproblem once and stores it. That one idea turns exponential algorithms into polynomial ones, and fills a large part of the GATE syllabus.

2 · Predict First

🤔

int fib(int n) { if (n <= 1) return n; return fib(n - 1) + fib(n - 2); }

How many calls (including the first) does fib(5) make?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

calls(n) = 1 + calls(n − 1) + calls(n − 2), calls(0) = calls(1) = 1: calls(2) = 3, calls(3) = 5, calls(4) = 9, calls(5) = 15.

Two ingredients

• Optimal substructure: an optimal solution is built from optimal solutions of subproblems.
• Overlapping subproblems: the same subproblems recur many times. (Divide and conquer has independent subproblems; DP has shared ones.)

Two styles

• Memoisation (top-down): keep the recursion, but store each result in a table on first computation; later calls just look it up.
• Tabulation (bottom-up): fill a table in an order where every entry's dependencies are already filled.

f[0] = 0; f[1] = 1;
for (i = 2; i <= n; i++) f[i] = f[i - 1] + f[i - 2];     // Θ(n) time

Space can often be cut to the last few entries (Fibonacci: two variables).

Counting calls

• Naive Fibonacci: calls(n) = 2·F(n + 1) − 1 (F = Fibonacci numbers): 15 for n = 5, 177 for n = 10: exponential.
• Memoised: each of fib(0) … fib(n) is computed once: Θ(n).

The DP recipe

• Define the subproblem (what does table entry T[i] or T[i][j] mean?).
• Write the recurrence (choices at the last step).
• Base cases.
• Order of filling.
• Where the answer is.

Time = (number of subproblems) × (time per subproblem).

Small DPs to see the recipe

• Grid paths: ways to walk from the top-left cell to the bottom-right cell of an m × n grid of cells, one step right or down at a time: P[i][j] = P[i − 1][j] + P[i][j − 1] → C(m + n − 2, m − 1).
• Kadane's maximum subarray (Lesson 4.1.1 in Θ(n)): best ending at i = max(A[i], best ending at i − 1 + A[i]); answer = max over i.

4 · Visual

Naive fib(5): 15 calls, fib(2) computed 3 times, fib(1) 5 times

                     fib5
              /              \
           fib4               fib3
         /      \            /    \
      fib3      fib2      fib2    fib1
     /   \      /  \      /  \
   fib2 fib1 fib1 fib0 fib1 fib0
   /  \
fib1 fib0
                    memoised: fib0..fib5 each computed once

5 · Worked Examples

Example 1 Easy

How many calls does naive fib(6) make?

Solution

1 + calls(5) + calls(4) = 1 + 15 + 9 = 25.

Example 2 Medium

Number of right/down paths from the top-left cell to the bottom-right cell of a 3 × 4 grid of cells?

Solution

2 downs and 3 rights in any order: C(5, 2) = 10.

Example 3 GATE

Which property distinguishes DP from divide and conquer?

Solution

Overlapping subproblems: DP reuses stored answers; D&C subproblems are independent.

6 · GATE Traps

⚠️

• Memoisation keeps recursion but stores results; it still costs stack space.
• Count distinct subproblems for DP time, not recursive calls.
• Naive Fibonacci calls = 2F(n + 1) − 1, exponential.
• DP needs optimal substructure and overlap; without overlap it is plain D&C.

7 · Memory Hook

🧠

"Solve each subproblem once, write it down."

8 · Connect the Dots

Phase 4 ended with problems where greedy fails. This lesson gave the fix in general; the next applies it to the first of those, the 0/1 knapsack.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1NAT1 markNaive calls

How many calls does naive fib(8) make?

Numerical answer: ________

Q2NAT2 marksNaive calls

How many calls does naive fib(10) make?

Numerical answer: ________

Q3MCQ1 markMemoised time

Memoised Fibonacci runs in:

• (A) Θ(n)
• (B) Θ(φⁿ)
• (C) Θ(n²)
• (D) Θ(log n)

Q4NAT2 marksGrid paths

Right/down paths from the top-left cell to the bottom-right cell of a 5 × 5 grid of cells?

Numerical answer: ________

Q5MSQ2 marksDP ingredients

Which are characteristic of problems solved by dynamic programming?

• (A) Overlapping subproblems
• (B) A greedy choice that is always safe
• (C) A table of subproblem answers
• (D) Optimal substructure

10 · Rule Card

• DP = optimal substructure + overlapping subproblems.
• Memoisation (top-down, store results) vs tabulation (bottom-up order).
• Time = #subproblems × time each. Naive fib calls = 2F(n+1) − 1; memoised Θ(n).
• Recipe: subproblem, recurrence, base, order, answer.

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

dynamic programmingoptimal substructureoverlapping subproblemsmemoisationtabulationDP recipenaive Fibonacci call countgrid pathsKadane's algorithm

12 · Answer Vault