DP foundations

ACompressed recap

🧾

DP = optimal substructure + overlapping subproblems; memoisation (top-down) vs tabulation (bottom-up); time = #subproblems × work each; naive Fibonacci calls 2F(n+1) − 1. 0/1 knapsack: K[i][w] = max(skip, take), Θ(nW) pseudo-polynomial, reconstruct by comparing rows. LCS: match → diagonal + 1, else max(up, left), Θ(mn); distinct LCSs by following ties.

BMerged rule card

5.1.1 Overlapping subproblems: memoisation vs tabulation; counting calls

• 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.

5.1.2 0/1 knapsack

• K[i][w] = max(K[i−1][w], vᵢ + K[i−1][w − wᵢ]) if wᵢ ≤ w, else K[i−1][w].
• Θ(nW) time; pseudo-polynomial; one row right-to-left.
• Reconstruct: item i taken iff K[i][w] ≠ K[i−1][w].

5.1.3 Longest common subsequence

• L[i][j] = L[i−1][j−1] + 1 on match; else max(L[i−1][j], L[i][j−1]); zeros on the borders.
• Θ(mn); reconstruct from (m, n); ties give multiple LCSs.
• Common substring: diagonal + 1 on match, else 0.

CInterleaved GATE-style questions

Q1NAT1 markCalls

Naive fib(6) calls?

Numerical answer: ________

Q2MCQ1 markMemoisation

Memoisation differs from tabulation in that it:

• (A) needs no table
• (B) is always faster
• (C) keeps the recursion and stores results on first computation
• (D) fills the table bottom-up in a fixed order

Q3NAT2 marksKnapsack

Items (weight, value): (5, 10), (4, 40), (6, 30), (3, 50); capacity 10. Maximum value?

Numerical answer: ________

Q4NAT2 marksKnapsack

Items (weight, value): (1, 2), (2, 3), (3, 5), (4, 6); capacity 6. Maximum value?

Numerical answer: ________

Q5NAT2 marksLCS

LCS length of AGGTAB and GXTXAYB?

Numerical answer: ________

Q6NAT2 marksLCS

LCS length of 10010101 and 010110110?

Numerical answer: ________

Q7MCQ1 markPseudo-polynomial

The knapsack DP is called pseudo-polynomial because its time Θ(nW):

• (A) depends on the numeric value of W, which can be exponential in its bit-length
• (B) is not correct for all inputs
• (C) is exponential in n
• (D) uses randomisation

Q8MSQ2 marksLCS facts

Which are true?

• (A) L[i][j] ≥ L[i − 1][j].
• (B) Two strings can have several distinct LCSs.
• (C) LCS runs in Θ(mn) time.
• (D) A common subsequence must be contiguous.

DAnswer Vault