Dynamic Programming

2 Nov 2025

1. Introduction

Dynamic Programming (DP) is a method that breaks a large problem into smaller problems, saves the answers to those smaller problems, and then gradually derives the answer to the original problem.

When different ways of solving a problem repeatedly encounter the same smaller problem, direct recursion performs repeated work. Dynamic programming stores these results in an array, so each state is calculated only once.

When writing a dynamic-programming solution, first determine four things:

What each state represents.
How the current state is derived from smaller states.
The initial values for the smallest states.
The order in which states must be calculated.

2. Basic Idea

The most common state form is dp[i]. It may represent the best answer among the first i elements, the number of ways to reach position i, or the best value of a sequence ending at position i.

After defining the state, examine the last step or the final choice. If the current state can be formed from several smaller states, this gives a transition equation. The states on the right side of that equation must be calculated first, so we often iterate through indices from small to large.

3. Example: Climbing Stairs

There are n stairs. At each move, you may climb one or two stairs. How many different ways are there to reach stair n?

Let dp[i] be the number of ways to reach stair i. There are only two possibilities for the final move:

Move one stair from stair i - 1.
Move two stairs from stair i - 2.

The two cases do not overlap, so:

dp[i] = dp[i - 1] + dp[i - 2];

Initially, dp[0] = 1 means that doing nothing is one valid way, and dp[1] = 1. After that, calculate the states from small to large.

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;

    vector<long long> dp(n + 1, 0);
    dp[0] = 1;
    if (n >= 1) dp[1] = 1;

    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    cout << dp[n];
    return 0;
}

For example, when n is 4, there are 5 ways: 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, and 2+2.

This example runs in O(n) time and uses O(n) space. Because dp[i] depends only on the previous two states, two variables can also be used to reduce the space complexity to O(1). The point of dynamic programming is not memorizing a formula, but clearly stating what every state represents and why it can be derived from earlier states.

Dynamic Programming

Related Posts