Python递归记忆化用list做字典键报unhashable type: 'list'错误如何解决？

报错原因 #

• Python 字典的键必须是可哈希的不可变类型，list是可变序列，支持增删改操作，没有实现固定的哈希映射规则，无法作为字典键使用，因此你把(n, lst)作为键存入memo时触发了unhashable type: 'list'错误。
• 你的代码还存在一处隐藏语法错误：末尾返回时写了memo(n,lst)，是把字典误作为函数调用，正确写法应该是memo[(n,lst)]。

修复方案 #

你不需要修改入参的lst类型，只需要在读写记忆字典时，临时将列表转为元组作为键即可，原列表的所有方法调用不受影响，修复后的可运行代码如下：

def find_num_changes_mem(n, lst, memo=None):
    lst.sort(reverse=True)
    if n < 0:
        return 0
    if len(lst) == 0:
        return 1 if n == 0 else 0
    if memo is None:
        memo = {}
    # 仅临时转元组生成字典键，原列表功能不受影响
    key = (n, tuple(lst))
    if key not in memo:
        if lst[0] > n:
            memo[key] = find_num_changes_mem(n, lst[1:], memo)
        else:
            memo[key] = find_num_changes_mem(n - lst[0], lst, memo) + find_num_changes_mem(n, lst[1:], memo)
    return memo[key]

print(find_num_changes_mem(5, [1,2,5,6], memo=None))

代码运行输出结果为4，对应4种符合要求的硬币兑换方案。

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