C++记忆化递归实现3和5凑N最小个数返回值异常问题

核心bug是你将递归过程中存储中间结果的temp3、temp5定义为了全局变量：
所有递归调用层级共享这两个变量的内存空间，内层递归执行时对temp3、temp5的赋值会直接覆盖外层调用已经暂存好的计算结果，导致后续判断取最小值时用到的数值根本不是当前层级算出来的有效值，最终返回结果错误。

你观察到的calculate(8)返回值异常，本质是递归内层执行时篡改了全局的temp3值，和记忆数组arr里存储的正确值无关——记忆数组本身的赋值逻辑没有问题，问题出在中间变量的作用域错误。

把temp3、temp5改为calculate函数内部的局部变量，让每个递归调用栈帧都拥有独立的中间变量存储空间，互不干扰。
额外可以删掉没有实际作用的全局变量N，避免全局命名空间污染。

修复后的完整代码：

#include <iostream>
using namespace std;

int arr[5001];

int calculate(int N) {
    if(arr[N]==0){
        // 改为局部变量，每个递归层独立存储
        int temp3 = calculate(N-3);
        int temp5 = calculate(N-5);
        if (temp3!=-1 && temp5!=-1){
            arr[N] = min(temp3, temp5) + 1;
        }
        else if (temp5!=-1) {
            arr[N] = temp5 + 1;
        }
        else if (temp3 != -1) {
            arr[N] = temp3 + 1;
        }
        else {
            arr[N] = -1;
        }
    }
    return arr[N];
}

int main()
{
    arr[1]=-1;arr[2]=-1;arr[3]=1;arr[4]=-1;arr[5]=1;
    int init;
    cin >> init;
    cout << calculate(init);
    return 0;
}

修复后输入11时，计算逻辑为：

• calculate(8)返回正确值2（3+5组合）
• calculate(6)返回正确值2（3+3组合）
• 最终取最小值2+1=3，对应组合3+3+5，符合预期结果。

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