csy の宝藏之地

核心理解

记忆化搜索和递推 DP 本质上都在做同一件事：定义状态、写出状态转移，并保证每个状态不会被重复计算。二者最大的区别不是转移方程，而是计算状态的方向。

记忆化搜索：从目标状态开始递归，需要哪个子状态才计算哪个子状态，属于自顶向下。
递推 DP：从最小状态开始按照依赖关系填表，最后得到目标状态，属于自底向上。
如果状态之间的依赖顺序不容易确定，记忆化搜索通常更自然。
如果计算顺序清晰、需要完整状态表，递推 DP 通常更直接，也没有递归栈风险。

一、记忆化搜索模板（自顶向下）

记忆化搜索可以理解为“递归 + 缓存”。每次进入一个状态时，先检查它是否已经计算过；如果计算过就直接返回，否则递归求解并把结果保存下来。

1. 一维状态（结果不可能是 -1 时）

当合法答案不可能为 -1 时，可以把整个 memo 数组初始化为 -1，用它同时表示“还没有计算”。

const int N = 100005;
int memo[N];

int dfs(int i) {
    // 1. 递归边界
    if (i == 0) return 0;          // 根据题目改写
    if (i == 1) return 1;

    // 2. 查表：已经计算过直接返回
    if (memo[i] != -1) return memo[i];

    // 3. 计算当前状态
    int res = 0;                   // 初始值根据题目，求最大可设 -INF
    // 枚举所有可能的前驱/子状态
    for (int k = 1; k <= i; k++) {
        res = max(res, dfs(i - k) + cost(k));
    }

    // 4. 存表并返回
    return memo[i] = res;
}

int main() {
    memset(memo, -1, sizeof(memo)); // 初始化
    cout << dfs(n) << endl;
}

其中 cost(k) 表示选择方案 k 所产生的贡献，需要根据具体题目替换。使用模板时还要确认递归过程一定会走向更小的子问题，避免产生循环依赖。

2. 一维状态（结果可能为 -1，需要 visited 数组）

如果 -1 也可能是合法答案，就不能继续用 memo[i] == -1 判断状态是否计算过。此时额外使用 vis 数组记录计算状态。

int memo[N];
bool vis[N];

int dfs(int i) {
    if (i == 0) return 0;
    if (vis[i]) return memo[i];   // 已计算过

    vis[i] = true;
    int res = -1e9;               // 这里结果可能取 -1，不能用 memo 判断
    for (int k = 1; k <= i; k++) {
        res = max(res, dfs(i - k) + cost(k));
    }
    return memo[i] = res;
}

vis[i] 只负责表示状态是否被计算，memo[i] 只负责保存答案，二者职责分开后不会和合法答案冲突。

3. 二维状态

二维记忆化搜索适合状态由两个变量共同决定的情况，例如数字三角形中的行和列、区间左右端点或网格坐标。

int n, m;
int memo[N][M];

int dfs(int i, int j) {
    // 边界条件
    if (i == n) return a[i][j];          // 示例：数字三角形最后一行
    if (j < 1 || j > m) return -1e9;

    // 查表
    if (memo[i][j] != -1) return memo[i][j];

    // 状态转移
    int res = max(dfs(i + 1, j), dfs(i + 1, j + 1)) + a[i][j];

    return memo[i][j] = res;
}

int main() {
    memset(memo, -1, sizeof(memo));
    cout << dfs(1, 1) << endl;
}

这里的状态含义是“从 (i, j) 出发能够获得的最大值”。先明确 dfs(i, j) 表示什么，再写边界和转移，代码会更不容易出错。

二、递推 DP 模板（自底向上）

递推 DP 必须确定计算顺序，保证计算当前状态时，它依赖的所有前驱状态都已经得到答案。它通常会计算全部状态，但没有递归栈溢出的风险。

1. 一维 DP

const int N = 100005;
int dp[N];

int solve(int n) {
    // 初始化最小子问题
    dp[0] = 0;
    dp[1] = 1;                    // 根据题目初始化

    // 按顺序递推
    for (int i = 2; i <= n; i++) {
        dp[i] = 初始值;            // 如 0 或 -1e9
        // 根据状态转移方程
        for (int k = 1; k <= i; k++) {
            dp[i] = max(dp[i], dp[i - k] + cost(k));
        }
    }
    return dp[n];
}

这个模板与一维记忆化搜索的转移完全对应，只是把递归调用改成了从小到大的循环。dp[i] 的初始值要与求最大值、最小值或计数等目标相匹配。

2. 二维 DP

int dp[N][M];

int solve() {
    // 初始化边界
    for (int j = 0; j <= m; j++) dp[0][j] = 0; // 根据题目
    for (int i = 0; i <= n; i++) dp[i][0] = 0;

    // 按行/列顺序递推
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            // 状态转移
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + a[i][j];
            // 或者多种情况取最优
            // dp[i][j] = max({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]});
        }
    }
    return dp[n][m];
}

二维 DP 的循环方向由依赖关系决定。上面的状态只依赖上方和左方，因此需要从上到下、从左到右计算；如果依赖方向发生变化，循环方向也要相应调整。

3. 二维 DP 滚动数组优化

当当前行只依赖上一行时，可以压缩空间：

int dp[2][M];

int solve() {
    // 初始化
    for (int j = 0; j <= m; j++) dp[0][j] = 0;

    for (int i = 1; i <= n; i++) {
        int cur = i & 1;          // 当前行
        int pre = cur ^ 1;        // 上一行

        dp[cur][0] = 0;           // 每行边界初始化
        for (int j = 1; j <= m; j++) {
            dp[cur][j] = max(dp[pre][j], dp[cur][j - 1]) + a[i][j];
        }
    }
    return dp[n & 1][m];
}

滚动数组把空间从 O(nm) 压缩到 O(m)。使用时要注意哪些旧状态仍然会被依赖，并在每一轮重新初始化必要的边界，防止残留数据影响答案。

三、两者对比与选择

对比项	记忆化搜索	递推 DP
方向	自顶向下	自底向上
实现	递归 + 缓存	循环 + 数组
状态顺序	不需要显式确定	必须确定计算顺序
计算量	只算需要状态	通常算所有状态
栈风险	递归深会栈溢出	无
适用情况	状态顺序复杂、图结构	顺序清晰、需要完整表

使用建议

先用一句话写清楚状态含义，例如：dp[i] 表示处理到第 i 个位置时的最优答案。
写出当前状态依赖哪些更小的状态，再决定使用递归还是循环。
检查边界、非法状态和初始值，尤其注意最大值问题中的负无穷。
状态访问稀疏或依赖关系复杂时优先考虑记忆化搜索。
状态顺序明确、数据规模较大或递归可能过深时优先考虑递推 DP。

无论选择哪一种写法，核心都不是背代码，而是先确定状态定义和状态转移方程。