More DP problems

ACompressed recap

🧾

Matrix chain: m[i][j] = min_k m[i][k] + m[k+1][j] + p_{i−1}p_k p_j; fill by length; Θ(n³); C_{n−1} parenthesisations. Subset sum R[x] |= R[x − s] (downward), Θ(nt). Coin ways: coins outer, W[x] += W[x − c]. Min coins: 1 + min D[x − c]. Rod cutting: max pᵢ + R[j − i]. LIS: best ending at i, Θ(n²). Edit distance: min(delete, insert, substitute), borders i and j, Θ(mn). Catalan: BSTs and parenthesisations.

BMerged rule card

5.2.1 Matrix-chain multiplication

• m[i][i] = 0; m[i][j] = min_k (m[i][k] + m[k+1][j] + p_{i−1}p_k p_j).
• Fill by chain length; s[i][j] stores the best k.
• Θ(n³) time, Θ(n²) space; parenthesisations C_{n−1}.

5.2.2 Subset sum, coin change and rod cutting

• Subset sum: R[x] |= R[x − s], x downward; Θ(n·t). Counting: +=.
• Coin ways: coins outer, amounts upward: W[x] += W[x − c].
• Min coins: D[x] = 1 + min D[x − c].
• Rod cutting: R[j] = max(pᵢ + R[j − i]); Θ(n²).

5.2.3 Longest increasing subsequence, edit distance and other sequence DPs

• LIS: L[i] = 1 + max L[j] (j < i, A[j] < A[i]); answer max L[i]; Θ(n²) (n log n possible).
• Edit distance: min(delete, insert, substitute/match); borders i and j; Θ(mn).
• BSTs on n keys: Catalan Cₙ.

CInterleaved GATE-style questions

Q1NAT2 marksMatrix chain

Dimensions p = (5, 10, 3, 12, 5, 50, 6). Minimum scalar multiplications?

Numerical answer: ________

Q2NAT2 marksMatrix chain

Dimensions p = (10, 100, 5, 50). Minimum scalar multiplications?

Numerical answer: ________

Q3NAT2 marksCoin ways

Ways to make 4 with coins {1, 2, 3} (order ignored)?

Numerical answer: ________

Q4NAT2 marksRod

Rod prices (lengths 1–5): 2, 5, 7, 8, 10. Maximum revenue for length 5?

Numerical answer: ________

Q5NAT2 marksSubset

Number of subsets of {1, 2, 3, 4, 5} summing to 10?

Numerical answer: ________

Q6NAT2 marksEdit

Edit distance between abc and yabd?

Numerical answer: ________

Q7NAT1 markLIS

LIS length of [10, 9, 2, 5, 3, 7, 101, 18]?

Numerical answer: ________

Q8MCQ1 markLoop order

In the coin-change "number of ways" DP, putting the amount loop outside and the coin loop inside counts:

• (A) ordered sequences (order matters)
• (B) combinations (order ignored)
• (C) the minimum number of coins
• (D) nothing meaningful

DAnswer Vault