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

GATE CSE Dynamic Programming PYQs

Standard yield5.9% of Algorithms

Dynamic Programming in GATE CS tests both classical tabular algorithms (such as Matrix Chain Multiplication and Rod Cutting) and structural properties of DP (su… Read the guide

Take topic test

Questions: 7
Asked: since 2011
Total marks: 11
Marks / paper: 0.5

7 GATE CSE Dynamic Programming PYQs with solutions, from Algorithms. Browse all GATE CSE PYQs.

Questions

Every official paper that asked this topic, newest first.

GATE CSE 2026 Set 2 · Q39Consider 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$ …MCQ2 marksMediumSolve
GATE CSE 2024 Set 2 · Q35Let $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 _________NAT1 markMediumSolve
GATE CSE 2021 Set 1 · Q40Define $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$ …MSQ2 marksMediumSolve
GATE CSE 2016 Set 2 · Q14The Floyd-Warshall algorithm for all-pair shortest paths computation is based onMCQ1 markEasySolve
GATE CSE 2016 Set 2 · Q38Let $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 _______.NAT2 marksMediumSolve
GATE CSE 2014 Set 2 · Q37Consider 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}}$ .NAT2 marksMediumSolve
GATE CSE 2011 · Q25An 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$ …MCQ1 markEasySolve

What GATE tests in Dynamic Programming

Concepts, patterns, formulas and traps distilled from past papers.

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
Commonmixed2 marks2021, 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
Commonmixed1 marks2024, 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
OccasionalMCQ2 marks2026
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
CommonMCQ1 marks2016
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
OccasionalNAT2 marks2014
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.