C++动态规划求解金矿网格问题代码TLE原因排查

你之前猜测的「三个方向递归返回值单独存储后再取最大值能提升性能」是错误的，两种写法在编译器优化下生成的执行逻辑完全一致，不会带来性能差异。真正导致TLE的是三个编码层面的问题：

• 核心性能杀手：矩阵参数值传递
  递归helper函数中vector<vector<int>> M使用值传递，每一次递归调用都会完整拷贝整个n*m大小的二维矩阵。记忆化递归的总调用次数为O(nm)级别，反复拷贝矩阵带来的时间开销直接飙升到O(n²m²)，数据规模稍大就会触发超时。将参数改为const vector<vector<int>>& M（常量引用传递）即可避免所有无意义的矩阵拷贝，这一步能解决90%以上的性能问题。
• 边界返回值引发整数溢出
  越界分支返回INT_MIN的写法存在未定义行为：INT_MIN和矩阵中存储的正黄金数相加时会触发有符号整数溢出，可能生成错误的极大值，干扰最大值判断逻辑，甚至触发多余的无效递归调用拖慢运行速度。正确的边界逻辑是所有超出地图范围的位置（行号<0、行号>=n、列号>=m）统一返回0，代表走到边界外后没有后续黄金收益，不需要用极小值标记无效路径。
• 冗余内存与判断开销
  初始化的dp数组N开辟了m+1列，专门存储列号等于m的边界状态，实际上该状态不需要落盘存储，遇到列号等于m时直接返回0即可，将dp数组改为n行m列就能减少不必要的内存分配和访问开销。此外递归中永远不会出现列号b<0的情况（所有移动都是列号+1，初始列号为0），该判断属于冗余逻辑可以直接删除。

class Solution{
public:
    int helper(int a , int b, int n , int m , const vector<vector<int>>& M, vector<vector<int>> &dp){
        // 越界统一返回0
        if(a < 0 || a >= n || b >= m){
            return 0;
        }
        // 命中记忆直接返回
        if(dp[a][b] != -1){
            return dp[a][b];
        }
        // 计算三个方向的最大收益
        int rightUpper = helper(a-1, b+1, n, m, M, dp);
        int right = helper(a, b+1, n, m, M, dp);
        int rightLower = helper(a+1, b+1, n, m, M, dp);
        return dp[a][b] = M[a][b] + max(rightUpper, max(right, rightLower));
    }
    int maxGold(int n, int m, vector<vector<int>> M)
    {
        vector<vector<int>> dp(n, vector<int>(m, -1));
        int ans = 0;
        for(int i = 0; i < n; i++){
            ans = max(ans, helper(i, 0, n, m, M, dp));
        }
        return ans;
    }
};

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