如何正确对最小硬币找零问题的递归实现进行记忆化优化？

你遇到的问题核心在于记忆化的状态定义错误，以及递归逻辑和记忆化机制不匹配。

为什么加记忆化会出错？ #

你的函数f(x, cnt, v)中，cnt是当前已使用的硬币数量，但你尝试仅用dp[x]存储结果——可相同的x可能通过不同路径到达，对应的cnt值差异很大，直接把dp[x]赋值为当前路径的ans，会导致后续调用时拿到的是之前某条路径的结果，而非当前场景下的最优解。

举个例子：假设x=5，第一次通过5-1（cnt=1）到达x=4，计算并存储了dp[4]；但另一次可能通过5-2（cnt=1）到达x=3，再到x=4时cnt=2，这时候dp[4]已经被之前的结果覆盖，就会返回错误的最小步数。

另外，你带着cnt累加的递归逻辑，本身就不符合记忆化的正确姿势——我们应该把dp[x]直接定义为凑出金额x所需的最小硬币数，这样递归函数不需要传递cnt，直接从子问题推导当前问题的解。

修正后的代码 #

我们重新调整递归逻辑和记忆化实现：

#include <vector>
#include <climits>
using namespace std;
using vi = vector<int>;

vi dp(1000001, -1);

int f(int x, const vi &v){
    if(x < 0) return INT_MAX;
    if(x == 0) return 0; // 凑0元需要0个硬币
    if(dp[x] != -1) return dp[x];
    
    int ans = INT_MAX;
    for(const int &i : v){
        int sub_result = f(x - i, v);
        // 只有子问题有有效解时，才更新当前答案，避免INT_MAX+1溢出
        if(sub_result != INT_MAX){
            ans = min(ans, sub_result + 1);
        }
    }
    dp[x] = ans;
    return ans;
}

关键改动说明 #

• 移除cnt参数：dp[x]直接存储凑出x的最小硬币数，递归时基于子问题x-i的结果加1（表示当前使用了一个硬币i）。
• 子问题有效性判断：当f(x-i)返回INT_MAX时，说明无法凑出x-i，此时不能用该子问题结果更新当前答案，避免数值溢出。
• 明确dp的含义：dp[x] = -1表示该状态未计算过，计算后存储的是最小硬币数，后续调用相同x时直接返回缓存结果。

额外注意事项 #

• 确保dp数组的大小足够覆盖你需要处理的最大x值，避免数组越界。
• 上述代码适用于完全背包场景（硬币可重复使用）；如果是0-1背包（每个硬币只能用一次），记忆化状态还需要加入已使用的硬币索引，不过从你的原始代码逻辑来看，应该是完全背包场景。

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