递归函数返回语句中Memoizing Vector未存储值问题排查

你的代码计算结果正确但记忆化未生效，核心问题出在递归中对状态参数j的修改，以及记忆化存储的索引位置错误，导致你误以为数组没存储值。

具体问题点 #

1. j被循环修改，导致记忆化存储到错误索引
   函数里用while (j<N)循环时，每次迭代都会让j递增，循环结束后j的值等于N。此时return my[mysum][j] = ways;是把结果存在my[mysum][N]的位置，但你main函数里的检查循环只遍历y<N的范围，完全没触及这个位置，所以输出check还是INT_MIN，误以为没存储。

2. 递归状态的逻辑冲突
   你的记忆化状态应该是(当前累计和mysum, 当前可选的起始索引j)，但循环中修改j会破坏这个状态的一致性，导致后续的记忆化判断和存储都对应错误的状态。

修复后的代码 #

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

long long solve(int N, int sum, int* coins, long long mysum, vector<vector<long long>> &my, int j) {
    if (mysum == sum) {
        return 1;
    }
    if (mysum > sum) {
        return 0;
    }
    // 检查当前状态是否已缓存
    if (my[mysum][j] != -1) {
        return my[mysum][j];
    }

    long long ways = 0;
    // 用for循环，不修改原参数j，保证状态的正确性
    for (int i = j; i < N; ++i) {
        ways += solve(N, sum, coins, mysum + coins[i], my, i);
    }
    // 存储当前状态(mysum, j)的结果
    return my[mysum][j] = ways;
}

int main() {
    int N = 3;
    int coins[] = {1, 2, 3};
    int sum = 4;
    int check = INT_MIN;
    vector<vector<long long>> my(sum + 1, vector<long long>(N + 1, -1));
    cout << solve(N, sum, coins, 0, my, 0) << " ";

    // 修改检查范围，遍历到y<=N，覆盖所有可能的存储位置
    for (int x = 0; x < sum + 1; ++x) {
        for (int y = 0; y <= N; ++y) {
            if (my[x][y] != -1) {
                check = 0;
            }
        }
    }
    cout << check;
    return 0;
}

修复说明 #

• 把while循环改成for循环，用局部变量i遍历，不修改函数参数j，确保记忆化存储的是当前状态(mysum, j)的结果。
• 调整main函数中的检查循环，遍历y<=N，这样就能检测到之前存储在my[mysum][N]位置的值，check会被设为0。
• 修复后记忆化数组会正确缓存每个状态的结果，递归重复计算的次数会大幅减少，解决耗时问题。

运行修复后的代码，输出会是4 0，说明记忆化已经生效。

内容的提问来源于stack exchange，提问作者Anurag-210