What are common examiner traps in Dynamic Programming?

Confusing contiguous subarray problems (solvable in O(n)) with non-contiguous subsequence problems (like general LIS/LNDS). Missing alternative optimal partitions in Rod Cutting (e.g., failing to count distinct combinations of piece lengths that yield the maximum revenue). Off-by-one errors in Matrix Chain Multiplication split index k or multiplying incorrect chain dimensions (pi-1pkpj). Assuming an alternative loop structure (such as anti-diagonal s = i+j) is incorrect without checking if all cell dependencies (i-1, j) and (i, j-1) have smaller index sums. Confusing the number of distinct LCS strings with the number of valid DP traceback paths/alignments. Off-by-one errors in indices when constructing string DP tables manually. Misclassifying dynamic programming graph algorithms (like Floyd-Warshall or Bellman-Ford) as greedy approaches (like Dijkstra's).

Dynamic Programming

7 Qs · since 2011 · 11 marks · 0.5 marks/paperStandard yield

Take topic test

Dynamic Programming in GATE CS tests both classical tabular algorithms (such as Matrix Chain Multiplication and Rod Cutting) and structural properties of DP (such as dependency gra… Guide

Type

GATE CSE 2026 Set 2Q39MCQ2 marksMediumConsider a table $T$ , where the elements $T[i][j], 0 \le i, j \le n$ , represent the cost of the optimal solutions of different subproblems of a problem that is being solved using a dynamic programming algorithm. The recursive formulation to compute the table entries is as follows: $T[0][k] = T[k][0] = 1 \quad \text{for } k = 0,1,2, \dots, n$ …
GATE CSE 2024 Set 2Q35NAT1 markMediumLet $A$ be an array containing integer values. The distance of $A$ is defined as the minimum number of elements in $A$ that must be replaced with another integer so that the resulting array is sorted in non-decreasing order. The distance of the array $[2, 5, 3, 1, 4, 2, 6]$ is _________
GATE CSE 2021 Set 1Q40MSQ2 marksMediumDefine $R_n$ to be the maximum amount earned by cutting a rod of length $n$ meters into one or more pieces of integer length and selling them. For $i > 0$ , let $\text{p}[i]$ denote the selling price of a rod whose length is $i$ meters. Consider the array of prices: $\text{p}[1] = 1, \text{p}[2] = 5, \text{p}[3] = 8, \text{p}[4] = 9, \text{p}[5] = 10, \text{p}[6] = 17, \text{p}[7] = 18$ …
GATE CSE 2016 Set 2Q14MCQ1 markEasyThe Floyd-Warshall algorithm for all-pair shortest paths computation is based on
GATE CSE 2016 Set 2Q38NAT2 marksMediumLet $A_1, A_2, A_3$ , and $A_4$ be four matrices of dimensions $10 \times 5, 5 \times 20, 20 \times 10$ , and $10 \times 5$ , respectively. The minimum number of scalar multiplications required to find the product $A_1A_2A_3A_4$ using the basic matrix multiplication method is _______.
GATE CSE 2014 Set 2Q37NAT2 marksMediumConsider two strings $A = \text{"qpqrr"}$ and $B = \text{"pqrqrp"}$ . Let $x$ be the length of the longest common subsequence (not necessarily contiguous) between $A$ and $B$ and let $y$ be the number of such longest common subsequences between $A$ and $B$ . Then $x + 10y = \underline{\hspace{1cm}}$ .
GATE CSE 2011Q25MCQ1 markEasyAn algorithm to find the length of the longest monotonically increasing sequence of numbers in an array $A[0:n-1]$ is given below. Let $L_i$ denote the length of the longest monotonically increasing sequence starting at index $i$ in the array. Initialize $L_{n-1} = 1$ . For all $i$ such that $0 \le i \le n-2$ …

Topic guide

What does GATE test in Dynamic Programming?

Dynamic Programming in GATE CS tests both classical tabular algorithms (such as Matrix Chain Multiplication and Rod Cutting) and structural properties of DP (such as dependency graphs, evaluation orders, and state-space reductions). Questions frequently require either manual tracing of a DP table on small concrete inputs or mapping an unfamiliar problem reduction (like array replacement distance) to a standard DP formulation like Longest Non-Decreasing Subsequence. Both conceptual evaluation order questions (MCQ/MSQ) and exact numerical optimization outputs (NAT) are regularly tested.

Core concepts

Optimal substructure and overlapping subproblems
Dependency graph / topological ordering of DP table evaluation (row-major vs diagonal/anti-diagonal traversals)
Matrix Chain Multiplication dynamic programming table construction
Rod Cutting DP and enumeration of distinct optimal partition solutions
Longest Non-Decreasing Subsequence (LNDS) and Longest Increasing Subsequence (LIS) reductions
Contiguous vs non-contiguous subsequence DP recurrences
Dynamic Programming Paradigm vs Greedy/Divide-and-Conquer
Longest Common Subsequence (LCS) calculation and traceback
Floyd-Warshall All-Pairs Shortest Path algorithm characterization

Recurring question patterns

Classical DP Table Optimization Tracing
common · mixed · 2 marks · 2021, 2016
Given a concrete instance of a standard DP problem (e.g., Matrix Chain Multiplication dimensions or Rod Cutting price arrays), manually compute the optimal cost/revenue or analyze the multiplicity of optimal solutions.
Reduction to Subsequence / Array DP
common · mixed · 1 marks · 2024, 2011
A problem is phrased as an array transformation (e.g., finding the distance to make an array sorted or finding longest increasing sequences) that reduces directly to Longest (Non-Decreasing/Monotonic) Subsequence.
DP Recurrence Dependency and Evaluation Order Analysis
occasional · MCQ · 2 marks · 2026
Given a 2D or 1D recurrence relation, analyze whether different iterative loop orderings (row-major, column-major, anti-diagonal $i+j=s$ , or backward traversal) respect the dependency graph and correctly compute all subproblems.
Design Paradigm Identification
common · MCQ · 1 marks · 2016
Direct identification of the algorithmic design technique (Greedy, Divide-and-Conquer, Dynamic Programming, etc.) underlying a classic standard algorithm.
DP Table Evaluation and Solution Enumeration
occasional · NAT · 2 marks · 2014
Tracing DP recurrences on specific short inputs (such as strings for LCS) to calculate optimal values (length) and counting the number of optimal solutions/alignments.

Formulas GATE uses

Matrix Chain Multiplication Recurrence

m[i, j] = \min_{i \le k < j} \{ m[i, k] + m[k+1, j] + p_{i-1} p_k p_j \}

Computing the minimum number of scalar multiplications required to multiply a chain of matrices with dimension sequence $\langle p_0, p_1, \dots, p_n \rangle$ .

Unbounded Rod Cutting Recurrence

R_n = \max_{1 \le i \le n} (p[i] + R_{n-i}) \quad \text{with } R_0 = 0

Computing the maximum revenue attainable by cutting a rod of length $n$ with given piece prices $p[1 \dots n]$ .

Minimum Replacements to Sort Array (via LNDS)

\text{Distance}(A) = n - \text{Length of LNDS}(A)

Finding the minimum number of element replacements needed to convert an array into a non-decreasing sorted sequence.

Contiguous Monotonic Subarray DP

L_i = \begin{cases} 1 + L_{i+1} & \text{if } A[i] < A[i+1] \\ 1 & \text{otherwise} \end{cases}

Computing the length of the longest contiguous monotonically increasing subarray starting at index $i$ .

Longest Common Subsequence (LCS) Recurrence

L[i, j] = \begin{cases} 0 & \text{if } i=0 \text{ or } j=0 \\ L[i-1, j-1] + 1 & \text{if } A[i] = B[j] \\ \max(L[i-1, j], L[i, j-1]) & \text{if } A[i] \neq B[j] \end{cases}

Computing the length of the longest common subsequence of two sequences $A$ and $B$ .

Floyd-Warshall All-Pairs Shortest Path Recurrence

D^{(k)}[i][j] = \min\left(D^{(k-1)}[i][j],\; D^{(k-1)}[i][k] + D^{(k-1)}[k][j]\right)

Updating shortest paths using vertex $k$ as an intermediate node.

Examiner traps in Dynamic Programming

Confusing contiguous subarray problems (solvable in O(n)) with non-contiguous subsequence problems (like general LIS/LNDS).
Missing alternative optimal partitions in Rod Cutting (e.g., failing to count distinct combinations of piece lengths that yield the maximum revenue).
Off-by-one errors in Matrix Chain Multiplication split index k or multiplying incorrect chain dimensions (pi-1pkpj).
Assuming an alternative loop structure (such as anti-diagonal s = i+j) is incorrect without checking if all cell dependencies (i-1, j) and (i, j-1) have smaller index sums.
Confusing the number of distinct LCS strings with the number of valid DP traceback paths/alignments.
Off-by-one errors in indices when constructing string DP tables manually.
Misclassifying dynamic programming graph algorithms (like Floyd-Warshall or Bellman-Ford) as greedy approaches (like Dijkstra's).

How questions are asked

Numerical calculation of optimal cost/multiplications (NAT)
MSQ testing both optimal DP value and structural properties/multiplicity of optimal solutions
Code/Pseudocode verification of DP table filling orders (MCQ)
Word-problem mapping to a classical DP recurrence (NAT/MCQ)
Algorithm paradigm identification MCQ
String DP computation and optimal solution count NAT

Paper trends

Shift from high-level paradigm recognition (e.g., identifying dynamic programming from a recurrence) to rigorous execution details such as verifying loop evaluation orders and topological correctness.
2026, 2011
Increased usage of NAT and MSQ formats to probe not just the optimal value, but also the number of alternative optimal solutions (multiset cuts) and reduction metrics.
2024, 2021, 2016
Questions range from direct 1-mark conceptual MCQ categorization of classical graph/DP algorithms to 2-mark computational NAT problems requiring full DP matrix execution and backtracking.
2016, 2014

Difficulty notes

Easy items test paradigm identification or straightforward 1D recurrence recognition. Medium items involve full manual evaluation of a 4-5 matrix chain, calculating unbounded knapsack/rod cutting up to $n=7$ with all optimal decompositions, or tracing dependency graphs across novel 2D loop orderings. Hard items typically introduce multi-constraint DP reductions or intricate state spaces.