Paint House III递归代码无法记忆化？DP问题求解思路咨询

代码背景 #

我针对LeetCode《Paint House III》编写了如下递归代码，能得出正确结果，但无法进行记忆化优化：

class Solution {
public:
    int countNeighborhoods(const vector<int>& houses) {
        int neighborhoods = 0;
        int m = houses.size();
        for (int i = 0; i < m; i++) {
            if (houses[i] != 0 && (i == 0 || houses[i] != houses[i - 1])) {
                neighborhoods++;
            }
        }
        return neighborhoods;
    }

    int solve(vector<int>& houses, vector<vector<int>>& cost, int m, int n, int target, int idx, int tCost) {
        if (idx >= m && target != 0)
            return 1000000;
        if (idx >= m && target == 0)
            return tCost;

        int ans = 1000000;
        
        if (houses[idx] != 0) {
            ans = min(ans, solve(houses, cost, m, n, target, idx + 1, tCost));
        } else {
            for (int i = 0; i < n; i++) {
                bool left_same = (idx > 0 && houses[idx - 1] == i + 1);
                bool right_same = (idx < m - 1 && houses[idx + 1] == i + 1);

                houses[idx] = i + 1;

                if (!left_same && !right_same) {
                    ans = min(ans, solve(houses, cost, m, n, target - 1, idx + 1, tCost + cost[idx][i]));
                } else {
                    ans = min(ans, solve(houses, cost, m, n, target, idx + 1, tCost + cost[idx][i]));
                }

                houses[idx] = 0;
            }
        }

        return ans;
    }

    int minCost(vector<int>& houses, vector<vector<int>>& cost, int m, int n, int target) {
        int initialNeighborhoods = countNeighborhoods(houses);
        int requiredNeighborhoods = target - initialNeighborhoods;
        if (requiredNeighborhoods < 0) return -1; 

        int ans = solve(houses, cost, m, n, requiredNeighborhoods, 0, 0);
        return (ans == 1000000) ? -1 : ans;
    }
};

以下是一段可实现记忆化的参考代码：

class Solution {
public:
    int solve(vector<int>& houses, vector<vector<int>>& cost, int m, int n, int target, int idx, int neighborhoods, int last_color) {
        if (idx == m) {
            return (neighborhoods == target) ? 0 : 1e6; // Cost 0 if exact neighborhoods; else, a large invalid cost.
        }
        if (neighborhoods > target) return 1e6; // Invalid if neighborhoods exceed target

        int ans = 1e6;
        if (houses[idx] != 0) {
            int new_neighborhoods = neighborhoods + (houses[idx] != last_color);
            ans = solve(houses, cost, m, n, target, idx + 1, new_neighborhoods, houses[idx]);
        } else {
            for (int color = 1; color <= n; color++) {
                int new_neighborhoods = neighborhoods + (color != last_color);
                int current_cost = cost[idx][color - 1] + solve(houses, cost, m, n, target, idx + 1, new_neighborhoods, color);
                ans = min(ans, current_cost);
            }
        }
        return ans;
    }

    int minCost(vector<int>& houses, vector<vector<int>>& cost, int m, int n, int target) {
        int result = solve(houses, cost, m, n, target, 0, 0, 0);
        return result == 1e6 ? -1 : result;
    }
};

问题与解答 #

1. 为何我的代码无法进行记忆化？若可优化，该如何修改？ #

你的代码没法做记忆化，核心原因是递归状态没有被完整、无歧义地描述：

• 你传递的target是剩余需要新增的街区数，但这个值依赖于之前修改过的houses数组状态——递归中会临时修改houses[idx]，而houses是全局共享的，不同递归分支修改后的houses状态不一样，但参数里没有记录这些关键信息，没法区分不同状态。
• 你用tCost累计当前花费，这个值是路径依赖的，不同路径到达同一个idx时tCost可能不同，但记忆化需要的是当前状态下的最小花费，而非把花费作为状态的一部分传递。

修改思路对齐参考代码的状态设计：

• 调整递归函数参数为：当前处理到第idx个房子、已形成的neighborhoods数量、上一个房子的颜色last_color（这三个参数唯一确定当前状态）。
• 去掉tCost参数，改为在递归中计算累计花费（当前颜色成本 + 后续递归的最小成本）。
• 不再提前计算requiredNeighborhoods，而是在递归过程中动态统计已有的街区数，和目标target对比。
• 新增三维记忆化缓存（比如memo[idx][neighborhoods][last_color]），存储已计算过的状态结果，避免重复计算。

2. 我在DP问题中常遇到类似情况：逻辑与正确解法接近，但实现细节导致无法记忆化或出错。这是否是DSA和竞赛编程中的常见问题？ #

这绝对是竞赛和DP学习中的高频问题。很多人能理清DP的核心逻辑，但在状态定义这个细节上踩坑——要么状态定义不全，导致不同场景被当成同一个状态；要么状态包含了不必要的路径信息，导致无法复用计算结果。

本质是对「DP状态的无后效性」理解不到位：一个合格的DP状态必须满足，当前状态的结果只和状态本身有关，和到达这个状态的路径无关。你的代码里把tCost和修改后的houses状态作为隐式依赖，违反了无后效性，自然没法记忆化。

3. 有没有通用技巧能让递归方案适配记忆化要求？ #

有几个通用思路可以帮你快速调整递归方案适配记忆化：

• 明确状态的核心维度：把所有影响后续决策的关键信息都放进递归参数里，比如当前位置、已完成的目标进度、前一个决策的关键结果（如上一个房子的颜色）。避免依赖外部可变变量（比如你修改的houses数组），尽量把所有状态都显式传递。
• 遵循无后效性原则：设计状态时，确保一旦状态确定，后续的最小/最大结果就是固定的，和怎么走到这个状态的过程无关。比如不要把累计花费作为状态参数，而是让递归函数返回当前状态下的最小花费，这样同一个状态只需要计算一次。
• 避免修改全局/共享变量：递归中如果修改了共享数组（比如你的houses），会导致不同递归分支的状态混淆，没法区分。如果必须修改，要么改完回溯后把关键信息记录到参数里，要么直接用参数传递状态（而非修改原数组）。
• 参考标准DP状态模板：对于常见的DP类型（如序列型、区间型），记住它们的典型状态定义方式。比如这类「序列决策+状态转移依赖前一个元素」的问题，通常会把「当前位置、当前累计状态、前一个元素的关键属性」作为核心状态维度。

内容的提问来源于stack exchange，提问作者Shreshth Sharma