C2100:illegal indirection错误排查——动态规划凑硬币问题

咱们先拆解你遇到的error C2100: illegal indirection错误，核心问题出在对unordered_map的操作逻辑和递归返回处理上，下面一步步分析：

1. 直接触发错误的核心问题 #

在递归函数里，当memo找不到当前n的记录时，你犯了两个关键错误：

• memo.insert(n, coinsValue);是错误用法：unordered_map::insert要求传入std::pair<int, int>类型的参数，而非两个单独的整数；
• 计算完coinsValue后直接返回iter->second：此时iter是memo.end()（因为刚才没找到对应key），访问end()迭代器的second属于非法内存操作，这就是报错的直接原因。

2. Base Case的逻辑漏洞 #

你的初始条件设置不够严谨：

• 遗漏了n == 0的情况：当金额为0时，应该返回1（代表“不使用任何硬币”这一种合法方式），这是递归的基础；
• 硬编码n == 1和n == 5的返回值完全没必要，反而会干扰递归逻辑——比如n=5时，通过递归计算coins(4)+coins(0)+coins(-5)+coins(-20)自然能得到正确结果2，不需要提前写死。

3. 修正后的完整代码 #

下面是修复并优化后的代码：

#include <iostream>
#include <unordered_map>

using namespace std;

int coins(int n, unordered_map<int, int>& memo) {
    // 正确的基础条件
    if (n < 0) {
        return 0;
    }
    if (n == 0) {
        return 1;
    }
    
    auto iter = memo.find(n);
    // 缓存存在则直接返回
    if (iter != memo.end()) {
        return iter->second;
    }
    
    // 递归计算四种硬币的组合数
    int coinsValue = coins(n - 1, memo) + coins(n - 5, memo) + coins(n - 10, memo) + coins(n - 25, memo);
    // 用[]操作直接存入缓存，比insert更简洁
    memo[n] = coinsValue;
    return coinsValue;
}

int coins(int n) {
    unordered_map<int, int> memo;
    return coins(n, memo);
}

int main() {
    cout << coins(10) << endl; // 输出4：对应10种组合方式为10个1、5+5、5+5个1、10
    return 0;
}

额外说明 #

• 用memo[n] = coinsValue替代insert更便捷：如果key不存在会自动插入，存在则覆盖，完美适配缓存需求；
• 这个实现是带记忆化的自顶向下DP，你也可以改成自底向上的DP方式（用数组存储每个金额的组合数），避免递归栈的开销。

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