动态规划优化掷骰子求和计数：记忆化数组错误排查

问题背景 #

给定w个点数范围1-6的骰子，计算掷出点数总和恰好为S的可能情况数（例如w=2、S=7时，结果为6）。原递归算法可行，但尝试用二维数组存储已计算结果做记忆化优化后输出错误，需排查问题。

原可行递归代码 #

def Amount(w, S):
    amount = 0
    if w == 0 and S == 0:
        amount = 1
    elif w == 0 and S > 0:
        amount = 0
    elif S < 0:
        amount = 0
    else:
        for number in range(1,7):
            subproblem = S - number
            amount = amount + Amount(w-1, subproblem) 

    return amount

错误的记忆化优化代码 #

memo = [[-1] * (S+1)] * (w+1) #create a 2-D array large enough to store the data (default = -1)

def AmountOptimized(w, S):
    amount = 0

    if memo[w][S] != -1: #if a value has already been calculated, use it
       return memo[w][S]
    
    if w == 0 and S == 0:
        amount = 1
    elif w == 0 and S > 0:
        amount = 0
    elif S < 0:
        amount = 0
    else:
        for number in range(1,7):
            subproblem = S - number
            amount = amount + AmountOptimized(w-1, subproblem)
            
    memo[w][S] = amount #when the calculation is done, store it

    return amount

错误根源 #

创建memo数组的方式存在致命问题：[[ -1 ] * (S+1)] * (w+1)会生成一个所有行引用同一个列表的二维数组。也就是说，memo中的每一行都是同一个对象的副本，当你修改memo[w][S]时，所有行的第S列都会被同步修改，完全破坏了记忆化存储的独立性，导致计算结果错误。

修正方案 #

使用列表推导式创建真正独立的二维数组，确保每一行都是独立的列表对象：

memo = [[-1]*(S+1) for _ in range(w+1)]

修正后的完整代码 #

为避免外部变量带来的问题，建议将memo初始化放在嵌套辅助函数内：

def AmountOptimized(w, S):
    # 初始化真正独立的二维记忆数组
    memo = [[-1]*(S+1) for _ in range(w+1)]
    
    def helper(w_sub, s_sub):
        amount = 0
        # 已计算过直接返回
        if memo[w_sub][s_sub] != -1:
            return memo[w_sub][s_sub]
        
        # 边界条件处理
        if w_sub == 0 and s_sub == 0:
            amount = 1
        elif w_sub == 0 and s_sub > 0:
            amount = 0
        elif s_sub < 0:
            amount = 0
        else:
            # 递归计算子问题
            for number in range(1,7):
                sub_s = s_sub - number
                amount += helper(w_sub - 1, sub_s)
        
        # 存储计算结果
        memo[w_sub][s_sub] = amount
        return amount
    
    return helper(w, S)

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