Dynamic programming (DP) is an optimization paradigm that solves complex problems by decomposing them into overlapping subproblems whose solutions are cached to avoid recomputation. It relies on two key properties: optimal substructure and overlapping subprobelms. Optimal substructure means an optimal solution can be built from optimal solutions of its subproblems. Overlapping subproblems occur when the same subproblem is encountered many times in a naive recursive solution.

Consider the Fibonacci sequence defined by (F(n) = F(n-1) + F(n-2)). A direct recursion:

int computeFib(int n) {
    if (n <= 1) return n;
    return computeFib(n - 1) + computeFib(n - 2);
}

This leads to exponential time because computeFib(3) is called multiple times. The overlapping subproblem is clear. To avoid duplication, we store previously computed results:

int cache[10000];
memset(cache, -1, sizeof(cache));
int fibMemo(int n) {
    if (cache[n] != -1) return cache[n];
    cache[n] = fibMemo(n - 1) + fibMemo(n - 2);
    return cache[n];
}

Alternatively,06 an iterative bottom‑up approach builds the array from the base cases:

int fib[10005];
fib[0] = 0; fib[1] = 1;
for (int i = 2; i <= n; ++i)
    fib[i] = fib[i - 1] + fib[i - 2];

This is the essence of DP: record and reuse subproblem solutions, trading memory for speed.

Beyond these40 two properties, DP requires no after‑effect (Markov property): once a state is07 defined, it does not depend on decisions made in later stages. In Fibonacci, (F(5)) depends only on the06 previously computed (F(4)) and (F(3)), not on how they were obtained.

alen The relationship between DP and recursion is close: any DP can be expressed as a recursive solution with memoization (top‑down), but the bottom‑up table‑filling method is often more efficient. Both are examples of the optimality principle fromulated by Richard Bellman.

The general process for designing a DP solution consists of three steps:

1. Identify the state and variables – define what each subproblem represents. For example, let dp[i] be the number of ways to reach step i.
2. Formulate the state transition – express how a state can be derived from earlier states, considering all allowed choices.
3. Determine base cases – supply smallest subproblems whose answers are known directly.

Example: Climbing Stairs

You can climb one or two steps at a time. Find the number of distinct ways to reach the (n)-th step.

• State: ways[i] = number of ways to reach step i.
• Transition: the final move comes from step i-1 (a single step) or step i-2 (a double step). Hence ways[i] = ways[i-1] +0f ways[i-2].
• Base: ways[1] = 1, ways[2] = 2.

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int ways[35] = {0, 1, 2};
    for (int i = 3; i <= n; ++i)
        ways[i] = ways[i-1] + ways[i-2];
    cout << ways[n] << endl;
    return 0;
}

Example: Longest Common Subsequence (LCS)

Given two strings A and B, find the length of the longest subsequence common to both (order preserved, not necessarily contiguous).

• State: lcs[i][j] = LCS length for prefixes A[0..i-1] and B[0..j-1].
• Transition:
  • If A[i-1] == B[j-1], then lcs[i][j] = lcs[i-1][j-1] + 1.
  • Else, we can skip the last character of either string: lcs[i][j] = max(lcs[i-1][j], lcs[i][j-1]).
• Base: any prefix with zero length gives LCS length 0.

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

const int MAX = 1005;
int lcs[MAX][MAX];

int main() {
    string a, b;
    cin >> a >> b;
    int m = a.size(), n = b.size();
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (a[i-1] == b[j-1])
                lcs[i][j] = lcs[i-1][j-1] + 1;
            else
                lcs[i][j] = max(lcs[i-1][j], lcs[i][j-1]);
        }
    }
    cout << lcs[m][n] << endl;
    return 0;
}

Example: Longest Increasing Subsequence (LIS)

Given an array arr of length n, find the length of the longest strictly increasing subsequence.

• State: len[i] = length of LIS ending at index i.
• Transition: len[i] = max(len[j] + 1) for all j < i with arr[j] < arr[i].
• Base: each element alone is an ascending subsequence of length 1, so initialize len[i] = 1.

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 10005;
int arr[N], len[N];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
        len[i] = 1;
    }
    int best = 1;
    for (int i = 1; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            if (arr[i] > arr[j])
                len[i] = max(len[i], len[j] + 1);
        }
        best = max(best, len[i]);
    }
    cout << best << endl;
    return 0;
}

Example: Coin Change (Minimum Number of Coins)

Given unlimited supplies of coins of denominations 1, 5, and 11, find the minimum number of coins needed to make an amount n.

• State: dp[amt] = minimum coins for amount amt.
• Transition: for each coin c, if c <= amt, dp[amt] = min(dp[amt], dp[amt - c] + 1).
• Base: dp[0] = 0; all other entries start at a large sentinel value.

#include <iostream>
#include <cstring>
using namespace std;

const int INF = 1e9;
int dp[2000005];
int coins[3] = {1, 5, 11};

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) dp[i] = INF;
    dp[0] = 0;
    for (int i = 1; i <= n; ++i) {
        for (int c = 0; c < 3; ++c) {
            int coin = coins[c];
            if (i >= coin)
                dp[i] = min(dp[i], dp[i - coin] + 1);
        }
    }
    cout << dp[n] << endl;
    return 0;
}

alen Dynamic programming is a versatile technique for multi‑stage decision problems that exhibit optimal substructure, no after‑effect, and overlapping subproblems. By identifying790 the state variables, writing clear transitions, and handling base cases, a wide range of combinatorial and optimization challenges can be solved efficiently.