为何Memoization在该最小成本递归解法中失效？如何修复？

你的核心错误是记忆化的状态维度缺失：

• 递归函数的状态由两个部分决定：当前处理到第idx个房子，以及当前允许选择的颜色（red/green/yellow三个布尔值）。
• 你只用memo[idx]缓存结果，相当于把所有不同颜色限制下的idx状态都当成了同一个，这会导致后续调用错误地复用不符合当前颜色限制的缓存值，最终输出错误结果。

修复步骤 #

1. 扩展记忆化缓存的维度：将memo改为二维数组，维度为n × 8（三个布尔值共有2^3=8种组合状态），用于存储(idx, 颜色允许状态)对应的最小成本。
2. 编码颜色状态：将三个布尔参数转换为一个整数（用三位二进制数表示，每一位对应一种颜色是否允许选择），作为缓存的第二维度索引。
3. 修正缓存的读写逻辑：递归时先检查memo[idx][state]是否已缓存，未缓存则计算并写入。

修改后的代码 #

class Solution {
public:
    int n;
    int memo[101][8]; // 第二维度对应8种颜色状态组合

    int minCost(vector<vector<int>>& costs) {
        n = costs.size();
        memset(memo, -1, sizeof(memo));
        // 初始状态：三种颜色都允许，编码为 1(red) + 2(green) +4(yellow) =7
        return dfs(costs, 0, true, true, true);
    }
    
    int dfs(vector<vector<int>>& costs, int idx, bool red, bool green, bool yellow) {
        if (idx == n) {
            return 0;
        }
        // 将三个布尔值编码为整数状态
        int state = (red ? 1 : 0) + (green ? 2 : 0) + (yellow ? 4 : 0);
        if (memo[idx][state] != -1) {
            return memo[idx][state];
        }
        int a = 1e9, b = 1e9, c = 1e9;
        if (red)
            a = dfs(costs, idx + 1, false, true, true) + costs[idx][0];
        if (green)
            b = dfs(costs, idx + 1, true, false, true) + costs[idx][1];
        if (yellow)
            c = dfs(costs, idx + 1, true, true, false) + costs[idx][2];
        
        return memo[idx][state] = min({a, b, c});
    }
};

额外说明 #

• 编码颜色状态时，1对应red允许，2对应green允许，4对应yellow允许，组合后的数值唯一标识当前的颜色限制状态。
• 修改后的时间复杂度降为O(n×8)=O(n)，因为每个(idx, state)组合只会计算一次，彻底解决了重叠子问题的重复计算。

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