Top-Down Memoization vs Bottom-Up Tabulation & Rolling-Array Space Compression

1. Top-Down Memoization vs. Bottom-Up Tabulation

Given the same state DAG $G = (V, E)$, how should we evaluate it?

• Top-Down Memoization (DFS Post-Order): Starts at the target state $t$ and recursively evaluates predecessors, caching results in a table or hash map.
  • When Top-Down Wins: When the state space $V$ is sparse—only a tiny fraction of states in the bounding box are actually reachable from the initial state (e.g., Digit DP with tight bounds, Game DP with strange step sizes, or Interval DP with sparse valid cuts).
  • Where Top-Down Loses: Recursion stack frames cost $32$–$64$ bytes per depth (risking stack overflow at depth $N = 10^5$), function call prologue/epilogue overhead, non-contiguous memory access, and inability to apply rolling-array space compression.
• Bottom-Up Tabulation (Explicit Topological Order): Iterates through nested loops in an order where all dependencies of state $x$ are already computed.
  • When Bottom-Up Wins: Dense state spaces where most states are visited, tight time limits requiring L1 cache locality and auto-vectorization (SIMD), or memory limits requiring $O(M)$ rolling-array compression instead of $O(N \cdot M)$.

2. Choosing the Inner Loop Direction for 1-Row Compression

When compressing $dp[i][j]$ into a 1D array $dp[j]$:

• If $dp[i][j]$ depends on $dp[i-1][j - w]$ (strictly smaller column from the previous row, as in 0/1 Knapsack), we must iterate $j$ backward ($W \to w$) so that when computing $dp[j]$, $dp[j - w]$ still holds its untouched value from row $i-1$.
• If $dp[i][j]$ depends on $dp[i][j - w]$ (smaller column from the current row, as in Unbounded Knapsack), we iterate $j$ forward ($w \to W$) so that $dp[j - w]$ already holds the updated row-$i$ value.
• If $dp[i][j]$ depends on $dp[i-1][j]$, $dp[i][j-1]$, and $dp[i-1][j-1]$ (as in Edit Distance / LCS), we iterate $j$ forward while saving the single overwritten diagonal scalar prev_diag = dp[j] in a temporary register!

3. Complexity Matrix

4. Reference C++20 Implementation

#include <algorithm>
#include <cstdint>
#include <string_view>
#include <vector>

// Space-Optimized O(min(N, M)) Longest Common Subsequence using 1 Row + 1 Diagonal Register
int lcs_rolling_one_row(std::string_view a, std::string_view b) {
    // Always make b the shorter string so our 1D array uses O(min(N, M)) space!
    if (a.size() < b.size()) std::swap(a, b);
    const int n = static_cast<int>(a.size());
    const int m = static_cast<int>(b.size());

    std::vector<int> dp(m + 1, 0);

    for (int i = 1; i <= n; ++i) {
        int prev_diag = 0; // Holds dp[i - 1][j - 1]
        for (int j = 1; j <= m; ++j) {
            int saved_up = dp[j]; // Save dp[i - 1][j] before overwriting dp[j]
            if (a[i - 1] == b[j - 1]) {
                dp[j] = prev_diag + 1;
            } else {
                dp[j] = std::max(dp[j], dp[j - 1]); // max(dp[i-1][j], dp[i][j-1])
            }
            prev_diag = saved_up; // Advance diagonal register for j + 1
        }
    }
    return dp[m];
}

// Two-Row Ping-Pong Template (i & 1) when transitions read multiple non-adjacent columns
long long min_falling_path_ping_pong(const std::vector<std::vector<int>>& grid) {
    const int n = static_cast<int>(grid.size());
    const int m = static_cast<int>(grid[0].size());
    constexpr long long INF = 1LL << 60;

    std::vector<long long> dp[2];
    dp[0].assign(grid[0].begin(), grid[0].end());
    dp[1].assign(m, INF);

    for (int i = 1; i < n; ++i) {
        const int cur = i & 1;
        const int prv = (i - 1) & 1;
        for (int j = 0; j < m; ++j) {
            long long best = dp[prv][j];
            if (j > 0) best = std::min(best, dp[prv][j - 1]);
            if (j + 1 < m) best = std::min(best, dp[prv][j + 1]);
            dp[cur][j] = grid[i][j] + best;
        }
    }
    const auto& last_row = dp[(n - 1) & 1];
    return *std::min_element(last_row.begin(), last_row.end());
}