Dynamic Programming: In-Depth Analysis and Practical Applications

Core Logic and Mathematical Principles

Dynamic Programming (DP) is not a specific code template, but a mathematical concept that involves topological sorting and pruning of state spaces. Its essence lies in decomposing a complex problem into several overlapping subproblems, saving the solutions of subproblems to avoid redundant calculations, ultimately leading to a global optimal solution.

The feasibility of DP is determined by three rigid mathematical criteria:

Optimal Substructure: The optimal solution of the global problem contains the optimal solutions of the subproblems. If we define a state $S$, its optimal value $V(S)$ must be formed by combining the optimal values $V(S')$ of its subset $\{S'\}$ through some monotonic operator (such as $\min, \max, +$).
No-aftereffect: This is the key to the validity of DP. Once the current state is determined, the evolution of all subsequent states depends only on the current state value, regardless of the path taken to reach that state (i.e., historical decisions). In graph theory terms, the state space must be mappable to a Directed Acyclic Graph (DAG), where states are vertices and decisions are directed edges.
Overlapping Subproblems: Different decision paths may reach the same substate. If the subproblem space is exponential, but the deduplicated actual state space is polynomial, then caching subproblem solutions (deduplication of solution space) can force the time complexity down from $O(2^N)$ or $O(N!)$ to $O(|V| + |E|)$.

State Design and Algorithm Derivation

Taking the classic linear recurrence problem as an example. Designing DP requires completing three hardcore derivations:

1. State Space Definition

Let $f[i]$ represent the local optimal solution after eliminating the first $i$ decision dimensions. Each dimension of the state must precisely correspond to boundary constraints and must completely obscure the historical path leading to that state.

2. State Transition Equation (Mathematical Mapping)

The state transition is essentially an edge weight relaxation operation on the DAG. For the target state $i$, its predecessor state set is $prev(i)$, and the transition cost is $w(j, i)$, thus the state transition equation is:

$$f[i] = \max_{j \in prev(i)} \{ f[j] + w(j, i) \}$$

3. Boundary Conditions and Topological Order

It is essential to clearly define the benchmark state (Base Case) without any predecessors, typically the initial assignments of $f[0]$ or $f[1]$. The computation of the entire state space must strictly follow the topological order of the DAG to ensure that when computing $f[i]$, all $j \in prev(i)$ have their $f[j]$ already solidified.

C++ Standard Source Code (NOIP Style)

The following is the core implementation of the Longest Increasing Subsequence (LIS) with a time complexity of $O(N^2)$, strictly adhering to the NOIP examination Linux environment compilation standards.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXN = 5005;
int a[MAXN];
int f[MAXN];

int main() {
    // Optimize standard input/output streams, sever synchronization with stdin/stdout to speed up I/O
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    if (!(cin >> n)) return 0;

    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }

    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        f[i] = 1; // Boundary condition: itself forms an independent team, length at least 1
        for (int j = 1; j < i; ++j) {
            if (a[j] < a[i]) {
                f[i] = max(f[i], f[j] + 1); // State transition: transferred from predecessor states satisfying no-aftereffect conditions
            }
        }
        ans = max(ans, f[i]); // Maintain global optimal solution
    }

    cout << ans << "\n";

    return 0;
}

NOIP Practical Pitfall Guide

1. Uninitialized State Array or Boundary Overflow

Phenomenon: The DP array is not explicitly initialized, leading to random garbage data participating in $max/min$ operations; or state calculations involving $f[i-1]$ cause array index overflow when $i=0$.
Avoidance Measures: It is essential to clarify predecessor states during the examination. If seeking the minimum value, the array must be fully initialized with memset filled with 0x3f, and explicitly assign valid starting points (e.g., $f[0]=0$). Loops involving $i-1$ should always start indexing from 1.

2. Aftereffect Pollution

Phenomenon: When calculating $f[i]$, using already modified state values from the same phase that should not have been used. This is common in the knapsack problem where the loop direction of the one-dimensional rolling array is incorrect.
Avoidance Measures: If the current state $f[i][j]$ depends on the previous stage's $f[i-1][j-v]$, and you choose to compress the first dimension, you must strictly enumerate $j$ in reverse order to prevent data pollution of subsequent states that have not yet been updated.

Classic NOIP/Luogu Problems

1. Luogu P1048 [NOIP2005 Popular Group] Herb Picking

Problem Description: Given a backpack capacity $T$ and $M$ items, each with picking time $t_i$ and value $v_i$, determine the maximum total value obtainable without exceeding the total time $T$.
Essence and Solution Approach: Classic 0-1 knapsack problem. Each item represents a decision, and the state space is limited by remaining time and the number of already decided items.
State Design: $f[j]$ represents the maximum value when the total time spent is exactly or not exceeding $j$.
Core Idea: Outer loop iterates over items $i$, and the inner loop traverses time $j$ in reverse from $T$ down to $t_i$. The transition equation is: $f[j] = \max(f[j], f[j - t_i] + v_i)$. The reverse order ensures that $f[j - t_i]$ still holds the historical optimal solution before including item $i$, perfectly aligning with the no-aftereffect condition.

2. Luogu P1091 [NOIP2004 Advanced Group] Choir Formation

Problem Description: $N$ students stand in a row, determine the minimum number of students that need to step out so that the remaining students form a peak-shaped queue like $t_1 < t_2 < \dots < t_k > t_{k+1} > \dots > t_N$.
Essence and Solution Approach: Bidirectional Longest Increasing Subsequence (LIS) problem. The entire sequence is divided by a turning point $k$ into a forward LIS on the left and a reverse LIS on the right.
State Design: $g[i]$ represents the length of the forward LIS ending at $s_i$; $h[i]$ represents the length of the reverse LIS starting at $s_i$.
Core Idea: Through $O(N^2)$ recurrence, calculate the $g$ and $h$ arrays from left to right and from right to left, respectively. Enumerate turning point $i$, then the maximum number of students retained with $i$ as the peak is $g[i] + h[i] - 1$. The final answer is $N - \max_{1 \le i \le N} \{g[i] + h[i] - 1\}$, using DP to eliminate the redundant complexity of overlapping subproblems.