AtCoder Educational DP Problem A部分测试用例运行时错误排查

• 核心错误出在minCost函数的参数传递规则上：你当前对h、dp两个数组使用的是值传递，每次递归调用都会拷贝整个数组，除了会产生极高的时间、内存开销外，最致命的问题是你对dp[n]的赋值只会修改当前函数栈里的局部副本，上层调用的dp数组完全不会更新，直接导致记忆化搜索失效。
• 当测试用例的n较小时（比如样例输入），就算没有记忆化，递归的计算量也足够小可以正常跑出结果；但当n较大时，大量重复计算会直接导致栈溢出或者超时，也就是你遇到的运行时错误。

只需要修改minCost的函数签名，把两个数组参数改为引用传递即可，修改后的函数头如下：

int minCost(int n, vector<int>& h, vector<int>& dp)

其余逻辑不需要改动，修改后记忆化就能正常生效，也不会有多余的数组拷贝开销，即可通过所有测试用例。

#include<bits/stdc++.h>
using namespace std;
#define int long long
 
int minCost(int n, vector<int>& h, vector<int>& dp) {
    if (dp[n] != -1) {
        return dp[n];
    }
    if (n == 1) {
        return dp[n] = 0;
    }
    if (n == 2) {
        return dp[n] = abs(h[1] - h[2]);
    }
 
    int oneStep = minCost(n - 1, h, dp) + abs(h[n] - h[n - 1]);
    int twoStep = minCost(n - 2, h, dp) + abs(h[n] - h[n - 2]);
    return dp[n] = min(oneStep, twoStep);
}
 
int32_t main() {
    int n;
    cin >> n;
    vector<int> h(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> h[i];
    }
    vector<int> dp(n + 1, -1);
    cout << minCost(n, h, dp);
    return 0;
}

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