Skip to content

DP Basics

This page introduces the fundamental concepts of dynamic programming, including the design of states and state transition equations, to help beginners gain a preliminary understanding of dynamic programming.

Other pages in this section will discuss methods for constructing dynamic programming models for various types of problems, as well as some optimization techniques for dynamic programming.

Introduction

[IOI1994] Number Triangle

Given a number triangle with \(r\) rows (\(r \leq 1000\)), find a path from the top to any point at the bottom that maximizes the sum of the numbers along the path. At each step, you can move to the point directly below to the left or directly below to the right.

1
2
3
4
5
        7 
      3   8 
    8   1   0 
  2   7   4   4 
4   5   2   6   5

In the example above, the optimal path is \(7 \to 3 \to 8 \to 7 \to 5\).

The simplest and most straightforward approach is to try all possible paths. However, since the number of paths is on the order of \(O(2^r)\), this method is unacceptable.

Notice an important fact: for an optimal path, every decision along the path is optimal.

Consider the optimal path mentioned in the example, focusing only on the first four steps \(7 \to 3 \to 8 \to 7\). There is no path from the top to the number at row 4, column 2 with a larger sum.

For each point, there are only two possible next decisions: move to the lower left or lower right (if they exist). Therefore, we only need to record the maximum sum up to the current point and use this value to make the next decision, updating the maximum sums for subsequent points.

This approach has another advantage: it successfully reduces the problem's scale by breaking it into multiple smaller subproblems. To find the optimal solution from the top to row \(r\), we only need information about the optimal solutions from the top to row \(r-1\).

However, there is still an issue: there may be many overlapping subproblems, and the same subproblem might be visited multiple times, which still leads to inefficiency. To solve this, we can store the solution to each subproblem and use memoization to control the order of access, ensuring each subproblem is visited only once.

The above outlines some basic ideas of dynamic programming. Below, we will introduce the concepts of dynamic programming more systematically.

Principles of Dynamic Programming

Problems solvable by dynamic programming must satisfy three conditions: optimal substructure, no aftereffects, and overlapping subproblems.

Optimal Substructure

Problems with optimal substructure may also be suitable for greedy algorithms.

Ensure that we consider all subproblems used in the optimal solution.

  1. Prove that the first component of the optimal solution involves making a choice.
  2. For a given problem, among its possible first choices, assume you know which choice leads to the optimal solution. You are not concerned with how this choice is obtained, only that it is known.
  3. Given the choice that yields the optimal solution, determine what subproblems this choice generates and how to best characterize the subproblem space.
  4. Prove that the solution to each subproblem, as part of the optimal solution to the original problem, is itself optimal. This is done by contradiction: assume a subproblem's solution is not optimal, then replace it with the optimal solution for that subproblem in the original solution, resulting in a better solution for the original problem, contradicting the assumption of optimality.

Keep the subproblem space as simple as possible, expanding only when necessary.

Optimal substructure can differ in two aspects:

  1. How many subproblems are involved in the optimal solution of the original problem.
  2. How many choices need to be examined when determining which subproblems to use in the optimal solution.

In the subproblem graph, each vertex corresponds to a subproblem, and the choices to be examined correspond to edges connecting the subproblem vertices.

No Aftereffects

Once a subproblem is solved, it is not affected by subsequent decisions.

Overlapping Subproblems

If there are many overlapping subproblems, we can store their solutions in memory to avoid repeatedly solving the same subproblems, thereby improving efficiency.

Basic Approach

For a problem solvable by dynamic programming, the general approach is as follows:

  1. Divide the original problem into several stages, each corresponding to several subproblems, and extract the characteristics of these subproblems (called states).
  2. Find all possible decisions for each state, or the ways states transition to each other (described mathematically as the state transition equation).
  3. Solve the problems for each stage in order.

Using graph theory concepts, we can construct a Directed Acyclic Graph (DAG), where each state corresponds to a node and decisions correspond to edges between nodes. The problem then transforms into finding the longest (or shortest) path in a DAG (see: DP on DAGs).

Longest Common Subsequence

Longest Common Subsequence Problem

Given a sequence \(A\) of length \(n\) and a sequence \(B\) of length \(m\) (\(n,m \leq 5000\)), find the longest sequence that is a subsequence of both \(A\) and \(B\).

The definition of a subsequence can be found in Subsequence. A brief example: the common subsequences of the strings abcde and acde include a, c, d, e, ac, ad, ae, cd, ce, de, acd, ade, ace, cde, acde. The length of the longest common subsequence is 4.

Let \(f(i,j)\) denote the length of the longest common subsequence when considering only the first \(i\) elements of \(A\) and the first \(j\) elements of \(B\). Finding this length is the subproblem. \(f(i,j)\) is what we call a state, and \(f(n,m)\) is the final state we aim to reach, which is the desired result.

For each \(f(i,j)\), there are three possible decisions: if \(A_i=B_j\), it can be appended to the end of the common subsequence; the other two decisions are to skip \(A_i\) or \(B_j\). The state transition equation is as follows:

\[ f(i,j)=\begin{cases}f(i-1,j-1)+1&A_i=B_j\\\max(f(i-1,j),f(i,j-1))&A_i\ne B_j\end{cases} \]

You can refer to the SourceForge LCS interactive webpage to better understand the implementation of LCS.

Reference Implementation 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
int n, m, a[MAXN], b[MAXM], f[MAXN][MAXM];

int dp() {
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
      if (a[i] == b[j])
        f[i][j] = f[i - 1][j - 1] + 1;
      else
        f[i][j] = std::max(f[i - 1][j], f[i][j - 1]);
  return f[n][m];
}

1
2
3
4
5
6
7
8
9
def dp(n, m, a, b):
    f = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if a[i] == b[j]:
                f[i][j] = f[i - 1][j - 1] + 1
            else:
                f[i][j] = max(f[i - 1][j], f[i][j - 1])
    return f[n][m]

The time complexity of this approach is \(O(nm)\).

Additionally, there exists an algorithm with time complexity \(O\left(\dfrac{nm}{w}\right)\) for this problem1. Interested readers are encouraged to explore it further.

Longest Non-decreasing Subsequence

Longest Non-decreasing Subsequence Problem

Given a sequence \(a\) of length \(n\) (\(n \leq 5000\)), find the longest subsequence of \(a\) such that each element is not less than the previous element.

Algorithm 1

Let \(f(i)\) denote the length of the longest non-decreasing subsequence ending with \(a_i\). The answer is \(\max_{1 \leq i \leq n} f(i)\).

When computing \(f(i)\), try to append \(a_i\) to other longest non-decreasing subsequences to update the answer. Thus, we can write the state transition equation: \(f(i)=\max_{1 \leq j < i,~a_j \leq a_i} (f(j)+1)\).

Reference Implementation 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
int n, a[MAXN], d[MAXN];

int dp() {
  d[1] = 1;
  int ans = 1;
  for (int i = 2; i <= n; i++) {
    d[i] = 1;
    for (int j = 1; j < i; j++)
      if (a[j] <= a[i]) {
        d[i] = std::max(d[i], d[j] + 1);
        ans = std::max(ans, d[i]);
      }
  }
  return ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def dp(n, a):
    d = [0] * (n + 1)
    d[1] = 1
    ans = 1
    for i in range(2, n + 1):
        d[i] = 1
        for j in range(1, i):
            if a[j] <= a[i]:
                d[i] = max(d[i], d[j] + 1)
                ans = max(ans, d[i])
    return ans

It is easy to see that the time complexity of this algorithm is \(O(n^2)\).

Algorithm 2

When \(n\) increases to \(n \leq 10^5\), the first approach is no longer fast enough. Below, we present an \(O(n \log n)\) solution.

Consider the previously defined state \((i, l)\), which indicates that the longest non-decreasing subsequence ending with the \(i\)-th element has length \(l\). Instead of processing states by fixing \(i\), we directly check whether \((i, l)\) is valid:

  • The initial state \((1,1)\) is always valid.
  • For any \((i, l)\), if there exists \(j < i\) such that \((j, l-1)\) is valid and \(a_j \le a_i\), then \((i, l)\) is valid.

Finally, we only need to find the \((i,l)\) with the largest \(l\) among all valid states to obtain the length of the longest non-decreasing subsequence.

Let the original sequence be \(a_1, \cdots, a_n\). Define an array \(d\), where the \(x\)-th position represents the minimum possible last element of a non-decreasing subsequence of length \(x\). Initially, the sequence is empty. Iterate \(i\) from \(1\) to \(n\), computing the longest non-decreasing subsequence for the first \(i\) elements. For the current element \(a_i\):

  • If \(a_i\) is greater than or equal to the last element of sequence \(d\), directly insert \(a_i\) at the end of \(d\).
    • Explanation: If \(a_i\) is greater than or equal to the last element of the current longest subsequence, it means there exists a non-decreasing subsequence that can include \(a_i\). Not inserting it would violate optimality.
  • If \(a_i\) is strictly less than the last element of \(d\), find the first element greater than \(a_i\) and replace it with \(a_i\).
    • Explanation: If inserted directly at the end, it would break the monotonicity of \(d\). The replacement ensures that the last element for each length is as small as possible, preserving more possibilities for subsequent elements.
    • Optimization: Since \(d\) is non-decreasing, we can use binary search to directly find the insertion position, reducing the overall complexity to \(O(n\log n)\) instead of the \(O(n^2)\) of brute-force search.

If we also need to output the specific longest non-decreasing subsequence, we can maintain an additional array \(d'_x\), which stores the position (choose any if multiple exist) of the minimum last element among all non-decreasing subsequences of length \(x\). During maintenance, when inserting \(a_i\) into \(d_x\), update \(d'_x\) to \(i\). Additionally, record the optimal predecessor \(p_i\) of \(i\) as \(d'_{x-1}\). Finally, starting from any state with maximum length, backtrack along the predecessors \(p_i\) to obtain the complete subsequence.

Reference Implementation 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
int n, a[MAXN], d[MAXN], di[MAXN], pre[MAXN], res[MAXN];

int dp() {
  int ans = 0;
  for (int i = 1; i <= n; ++i) {
    int tmp = std::upper_bound(d, d + ans, a[i]) - d;
    pre[i] = tmp ? di[tmp - 1] : -1;
    d[tmp] = a[i];
    di[tmp] = i;
    if (tmp == ans) ++ans;
  }
  // Construct the subsequence.
  for (int k = ans, i = di[ans - 1]; k; --k) {
    res[k] = a[i];
    i = pre[i];
  }
  return ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
n = 0
a = [0] * MAXN
d = [0] * MAXN
di = [0] * MAXN
pre = [0] * MAXN
res = [0] * MAXN


def dp():
    ans = 0
    for i in range(1, n + 1):
        tmp = bisect.bisect_right(d, a[i], 0, ans)
        pre[i] = di[tmp - 1] if tmp else -1
        d[tmp] = a[i]
        di[tmp] = i
        if tmp == ans:
            ans += 1

    # Construct the subsequence
    k = ans
    i = di[ans - 1]
    while k:
        res[k] = a[i]
        i = pre[i]
        k -= 1

    return ans

The time complexity of this algorithm is \(O(n\log n)\). The time complexity for outputting the answer is \(O(\textit{ans})\).

Note

For the longest increasing subsequence problem, similarly, we can let \(d_i\) represent the minimum last element among all longest increasing subsequences of length \(i\).

Note that in step 2, if \(a_i \leq d_{len}\), since adjacent elements in a longest increasing subsequence cannot be equal, we need to find the first element in \(d\) that is not less than \(a_i\) and replace it with \(a_i\).

In implementation (using C++ as an example), change the upper_bound function to lower_bound.

References and Notes

  1. Bitwise Operations for Longest Common Subsequence - -Wallace- - Blog Garden ↩

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用