Deep Dive into the Perfect Combination of Memoization and Topological Sorting

Core Logic and Mathematical Principles

For many complex or hidden state spaces, the dependencies between states are not as intuitive as linear loops. If nested loops are forced, it is easy to lead to the use of uninitialized states due to the difficulty in determining the computation order.

Memoization and Topological Sorting are philosophically equivalent:

1. Essence of Topological Order: If the computation of state $A$ depends on state $B$, then there must be a directed edge $B \to A$ in the state graph (DAG). The purpose of topological sorting is to establish a total order such that all starting points of edges are placed before their endpoints.
2. Recursive Form of Topological Sorting (DFS): Memoization implicitly completes the topological sorting of the state graph using the system stack of Depth-First Search (DFS) from a reverse perspective of dynamic programming (starting from the target state and recursively querying predecessor states). When all successor/predecessor states of a state have been visited and are about to be popped from the stack, the global optimal solution for that state has been solidified.
3. Core Operator to Eliminate Redundancy: Memoization introduces a memoization array f that is isomorphic to the state space (usually initialized to an unvisited marker, such as -1). In the recursive branches, once it is found that f[state] has already been computed, it immediately returns in $O(1)$. Geometrically, this is equivalent to directly cutting off all subgraphs that have been visited multiple times in the DAG, forcing the exponential complexity of the search back to the sum of the number of vertices and edges in the graph: $O(|V| + |E|)$.

State Design and Algorithm Derivation

Taking the classic graph theory model "Skiing" (the longest path in a DAG) as an example, we derive the execution process of memoization:

1. State Design

Let state $f[i][j]$ represent the maximum area length that can be skied starting from the grid coordinates $(i, j)$ (i.e., the number of edges in the longest path starting from that grid point $+ 1$).

2. Transition Equation and Recursive Form

Since one can only ski in lower terrain directions, define $(nx, ny)$ as the neighbors of $(i, j)$ that satisfy $h[nx][ny] < h[i][j]$. The transition equation is expressed as a typical successor maximum relaxation:

$$f[i][j] = 1 + \max_{(nx, ny) \in \text{valid\_neighbors}(i, j)} \{ f[nx][ny] \}$$

If there are no lower terrains around the current point, this grid point acts as a source point with an in-degree of 0 in the DAG (considered as a terminal point in reverse), $f[i][j] = 1$.

3. Memoization Logic

Define the search function int dfs(int x, int y):

• Cache Hit: If f[x][y] != 0 (assuming initialized to 0), it indicates that this node has been solidified in the previous topological traversal, and f[x][y] is returned directly.
• Cache Miss Calculation: Traverse in four directions; if conditions are met, recursively call dfs(nx, ny) and update the current node with the return value.
• Backtracking Solidification: At the end of all branch traversals, write the final computed result into f[x][y] and return.

C++ Standard Source Code (NOIP Style)

The following is the implementation of the longest descending path based on memoization, strictly compiled according to Linux g++ -O2 standards.

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

using namespace std;

const int MAXN = 105;
int h[MAXN][MAXN];
int f[MAXN][MAXN]; // Memoization array, 0 indicates not accessed
int n, m;

// Direction vector arrays
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

int dfs(int x, int y) {
    // Fatal pitfall: if already computed, must return directly, otherwise memoization fails and degenerates into pure brute force search
    if (f[x][y] != 0) {
        return f[x][y];
    }

    f[x][y] = 1; // Initialize: the node itself counts as at least one length

    for (int i = 0; i < 4; ++i) {
        int nx = x + dx[i];
        int ny = y + dy[i];

        // Boundary check and strict descent condition
        if (nx >= 1 && nx <= n && ny >= 1 && ny <= m) {
            if (h[nx][ny] < h[x][y]) {
                f[x][y] = max(f[x][y], dfs(nx, ny) + 1); // Implicit topological order transition
            }
        }
    }

    return f[x][y]; // At this point, the longest path for this node in the DAG has been completely solidified
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

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

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            cin >> h[i][j];
            f[i][j] = 0; // 0 initialization indicates all states are unvalued
        }
    }

    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            ans = max(ans, dfs(i, j)); // Multi-source DFS to find the global longest path
        }
    }

    cout << ans << "\n";

    return 0;
}

NOIP Practical Pitfall Guide

1. Memoization Array Not Assigned Correct "Unvisited" Marker Value

• Phenomenon: Valid DP state values may include 0 (e.g., the number of schemes is 0, or the maximum profit is 0). If the memoization array is initialized to 0 and the code contains if (f[state] != 0) return f[state];, the program will mistakenly consider those truly "valid zero states" as uncalculated, leading to massive repeated searches and causing TLE (Time Limit Exceeded).
• Avoidance Method: If the state value can be 0, the memoization array must be initialized to -1. At the beginning of the search, use if (f[state] != -1) return f[state]; for deduplication.

2. Hidden Loops in State Transition Graph Cause System Stack Overflow

• Phenomenon: Memoization relies on the state space being a DAG. If the state design is improper, leading to transitions having loops (e.g., state $A$ depends on $B$, and $B$ depends on $A$), unconditional recursion will enter an infinite loop, resulting in an instant Runtime Error (Segmentation Fault), which is a fatal stack overflow in the exam.
• Avoidance Method: Strictly check whether the transition conditions have monotonicity (such as height decreasing, time increasing, scale decreasing). If there is no monotonicity, a vis[state] array must be added to mark "currently visiting". Once it is found that the next state’s vis is already true in the recursive branch, it indicates that there is a loop in the graph, and pruning or redesigning the state must be done immediately.

Classic NOIP/Luogu Problems

1. Luogu P1434 [SHOI2002] Skiing

• Problem Description: Given a two-dimensional grid, each grid point has a height. A person can ski in the up, down, left, and right directions, provided that the height of the next grid is strictly less than the current grid. Find the length of the longest skiing path.
• Essence and Solution Approach: The implicit topological order longest path problem based on the monotonicity of grid heights.
• State Design: $f[i][j]$ represents the maximum length of skiing starting from $(i,j)$.
• Core Idea: The strict monotonic decrease in height ensures that the state space absolutely has no loops (no aftereffects). Directly perform DFS on each point, using the four direction vectors to attempt transitions. If the neighbor height is lower, it contributes to the current state via dfs(nx, ny) + 1. Since memoization is used, each grid point will only be fully computed once.

2. Luogu P1464 Function

• Problem Description: Given a complex branching definition of a third-order recursive function $w(a, b, c)$. When $a, b, c$ satisfy various size relationships, the function will recursively call itself (e.g., $w(a-1, b, c) + w(a-1, b-1, c) - w(a-1, b, c-1)$). It requires inputting multiple groups of $a, b, c$ and quickly outputting the function values.
• Essence and Solution Approach: Deduplication of repeated subproblems in high-dimensional scalar functions. Ordinary brute force recursion can lead to an explosive time complexity of $O(3^N)$ due to numerous branches.
• State Design: Since there are constant boundaries when $a,b,c \le 0$ or $>20$, the actual effective state space is only a three-dimensional grid of $25 \times 25 \times 25$. Let $f[a][b][c]$ store the corresponding computed values.
• Core Idea: First handle the boundary special cases of $a,b,c$ (return 1 if less than or equal to 0, convert to 20 if greater than 20). For points within the effective range, directly check whether f[a][b][c] already has a value before recursive computation. If so, return immediately. Through memoization, the exponential brute force search is forcibly suppressed to a constant-level lookup of $O(20^3)$.