Introduction
Dynamic Programming (DP) is one of the most powerful algorithm-design techniques in computer science and a permanent favourite of examiners. In BCS (technical/IT cadre), Bangladesh Bank / other bank IT-officer, and BCC / DoICT written and MCQ tests, DP appears through direct definition questions ("What is optimal substructure?"), classic named problems (Fibonacci, 0/1 Knapsack, Longest Common Subsequence, Matrix Chain, Coin Change), complexity comparisons (recursion vs memoization vs tabulation), and short numeric worked problems you must solve by hand.
At its heart, DP is a disciplined way of not solving the same subproblem twice. When a big problem can be broken into overlapping smaller problems, DP solves each small problem once, stores the answer, and reuses it — trading a little memory for an enormous saving in time (often turning exponential algorithms into polynomial ones). This lesson builds the idea from first principles, defines every term precisely, and drills the exact problems examiners reuse year after year.
Learning objectives
- Define dynamic programming and state precisely the two conditions (optimal substructure and overlapping subproblems) a problem must satisfy for DP to apply.
- Distinguish DP from divide and conquer and from plain greedy methods.
- Explain and implement both DP styles: top-down memoization and bottom-up tabulation.
- Formulate a DP by identifying its state, recurrence (transition), base cases, and answer.
- Solve by hand the standard exam problems: Fibonacci, 0/1 Knapsack, Longest Common Subsequence (LCS), Coin Change, and Matrix Chain Multiplication.
- Analyse the time and space complexity of a DP and apply space-optimisation.
- Avoid the common conceptual and arithmetic mistakes examiners test.