Dynamic Programming Basics

This page mainly introduces the basic ideas of dynamic programming, as well as approaches to designing states and state transition equations in dynamic programming, helping beginners gain a preliminary understanding.

Other pages in this section introduce methods for building dynamic-programming models for various types of problems, as well as various optimization techniques for dynamic programming.

Introduction

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

The simplest brute-force idea is to try all paths. Since the number of paths is on the order of $O(2^r)$, this approach is unacceptable.

Notice the following fact: every decision made along an optimal path is itself optimal.

For the optimal path mentioned in the example, consider only the first four steps, $7 \to 3 \to 8 \to 7$. There is no path from the top to the $2$-nd number in the $4$-th row with a greater weight.

For each point, there are only two choices for the next step: move down-left or down-right (if it exists). Therefore, we only need to record the maximum weight at the current point and use this maximum weight to make the next decision, updating the maximum weights of subsequent points.

This has another benefit: we successfully reduce the problem size by dividing one problem into multiple smaller problems. To obtain the optimal solution from the top to the $r$-th row, we only need the information about the optimal solution from the top to the $r-1$-th row.

There is still a problem: the overlapping parts among subproblems are numerous, and the same subproblem may be visited repeatedly, so the efficiency remains low. The solution is to store the solution to each subproblem and use memoization to restrict the visitation order, ensuring that each subproblem is visited only once.

These are some basic ideas of dynamic programming. The following sections will introduce the ideas of dynamic programming more systematically.

Principles of dynamic programming

Problems solvable by dynamic programming need to satisfy three conditions: optimal substructure, no aftereffect, and overlapping subproblems.

Optimal substructure

Having optimal substructure may also indicate that a problem is suitable for a greedy solution.

Make sure that all subproblems used in the optimal solution are considered.

1. Prove that the first component of an optimal solution to the problem is making a choice;
2. For a given problem, among its possible first-step choices, assume that you already know which choice will produce an optimal solution. You do not care how this choice was obtained; simply assume that it is already known;
3. Given the choice that yields an optimal solution, determine which subproblems this choice produces and how to best characterize the subproblem space;
4. Prove that, as components of the optimal solution to the original problem, the solution to each subproblem is itself optimal. Use proof by contradiction: suppose the solution added for a subproblem is not its own optimal solution. Then replace the current non-optimal solution in the original problem with the subproblem's optimal solution to obtain a better solution to the original problem, contradicting the assumption that the original solution is optimal.

Keep the subproblem space as simple as possible and expand it only when necessary.

The differences in optimal substructure appear in two aspects:

1. How many subproblems are involved in the optimal solution to the original problem;
2. How many choices must be considered when determining which subproblems are used by the optimal solution.

Each vertex in a subproblem graph corresponds to a subproblem, while the choices that need to be considered correspond to edges incident to the subproblem vertices.

No aftereffect

A subproblem that has already been solved will not be affected by subsequent decisions.

Overlapping subproblems

If there are many overlapping subproblems, we can use space to store their solutions, avoiding repeated solutions of the same subproblems and thereby improving efficiency.

Basic idea

For a problem solvable by dynamic programming, the following approach is generally used:

1. Divide the original problem into several stages, with each stage corresponding to several subproblems, and extract the features of these subproblems (called states);
2. Find the possible decisions for each state, or the transitions among states (described mathematically as the state transition equations);
3. Solve the problems in each stage in order.

From the perspective of graph theory, construct a directed acyclic graph, where each state corresponds to a node in the graph and decisions correspond to edges between nodes. The problem is thereby transformed into finding a longest (shortest) path on a DAG (see DP on a DAG).

Longest common subsequence

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, and 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 the length of the longest common subsequence in this situation is the subproblem. $f(i,j)$ is the state described above, and $f(n,m)$ is the final state to be reached, namely the desired result.

For each $f(i,j)$, there are three 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:

See SourceForge's interactive LCS page for a better understanding of the LCS implementation process.

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];
}

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]

This method has time complexity $O(nm)$.

In addition, this problem has an $O\left(\dfrac{nm}{w}\right)$ algorithm¹. Interested students can explore it on their own.

Longest non-decreasing subsequence

Algorithm 1

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

When calculating $f(i)$, try appending $a_i$ to the ends of other longest non-decreasing subsequences to update the answer. Thus, the following state transition equation can be written: $f(i)=\max_{1 \leq j < i,~a_j \leq a_i} (f(j)+1)$.

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;
}

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 this algorithm has time complexity $O(n^2)$.

Algorithm 2

When the range of $n$ expands to $n \leq 10^5$, the first approach is no longer fast enough. The following gives an $O(n \log n)$ approach.

Consider the previously defined state $(i, l)$, representing that the longest non-decreasing subsequence ending at the $i$-th element has length $l$. Unlike the previous method, which processes states by fixed $i$, here we directly determine whether $(i, l)$ is valid:

• The initial state $(1,1)$ is necessarily valid.
• For any $(i, l)$, if there exists a $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 valid state $(i,l)$ with the largest $l$ to obtain the length of the longest non-decreasing subsequence.

Let the original sequence be $a_1, \cdots, a_n$, and define an array $d$, where the $x$-th position stores the minimum possible final element of a non-decreasing subsequence of length $x$. Initially the sequence is empty. Let $i$ iterate from $1$ to $n$, and successively find the length of the longest non-decreasing subsequence among the first $i$ elements. For the current element $a_i$:

• If $a_i$ is greater than or equal to the last element in sequence $d$, directly insert $a_i$ at the end of sequence $d$.
  • Explanation: if $a_i$ is greater than or equal to the final element of the current longest subsequence, a non-decreasing subsequence exists that can append $a_i$. Not inserting it would destroy optimality.
• If $a_i$ is strictly smaller than the last element in $d$, find the first element greater than it and replace that element with $a_i$.
  • Explanation: inserting it at the end would destroy the monotonicity of $d$; replacement ensures that the final element for each length is as small as possible, preserving more possibilities for subsequent elements.
  • Optimization: because $d$ is non-decreasing, binary search can directly find the insertion position, reducing the overall complexity to $O(n\log n)$ instead of the $O(n^2)$ complexity of brute-force searching.

If the actual longest non-decreasing subsequence must also be output, additionally maintain an array $d'_x$, representing the position of the minimum final element among non-decreasing subsequences of length $x$ (if there are several, any one may be chosen). During maintenance, when inserting element $a_i$ into $d_x$, simultaneously update $d'_x$ to $i$. Also record the optimal predecessor $p_i$ of $i$ as $d'_{x-1}$. Finally, starting from any valid state of maximum length and tracing backward along predecessors $p_i$, the complete subsequence can be obtained.

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;
}

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

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

References and notes

• Detailed explanation of the nlogn algorithm for the longest non-decreasing subsequence - lvmememe - Cnblogs