Python二维递归动态规划实现陷入无限循环问题排查

问题背景 #

来自《量化金融面试实用指南》编号5.3的动态卡牌游戏，其递推公式为：
E[f(b,r)] = max(b−r,(b/(b+r))∗E[f(b−1,r)]+(r/(b+r))∗E[f(b,r−1)])
边界条件：
f(0,r)=0, f(b,0)=b

你实现的递归代码如下：

def f(b,r):
    if b == 0:
        return 0
    elif r == 0:
        return b
    else:
        var = (b/(b+r)) * f(b-1, r) + (r/(b+r)) * f(b, r-1) 
        return max( b-r,  var )

print("The solution is")
print(f(26,26))

该代码在处理f(5,5)这类小输入时正常返回结果，但处理f(26,26)时迟迟无法返回，并非无限循环，而是重复计算导致的指数级时间复杂度。

问题原因 #

递归过程中，大量(b,r)组合会被反复计算：比如计算f(26,26)时会调用f(25,26)和f(26,25)，而这两个子问题又都会调用f(25,25)，f(25,25)又会触发更多重复的子问题。随着b和r数值增大，总计算量呈爆炸式增长，看似“卡住”实际是在做大量重复运算，耗时极长。

优化方案 #

方案1：记忆化缓存（Memoization） #

用缓存存储已经计算过的(b,r)结果，避免重复计算，可通过Python内置的lru_cache装饰器快速实现：

from functools import lru_cache

@lru_cache(maxsize=None)
def f(b, r):
    if b == 0:
        return 0.0
    elif r == 0:
        return float(b)
    else:
        var = (b/(b+r)) * f(b-1, r) + (r/(b+r)) * f(b, r-1)
        return max(b - r, var)

print("The solution is")
print(f(26,26))

lru_cache会自动缓存函数的输入参数与对应返回值，每个(b,r)组合仅计算一次，时间复杂度降至O(b*r)，能快速处理大输入。

方案2：迭代式动态规划（自底向上） #

从边界条件出发，按顺序计算所有小的(b,r)组合，逐步推导到目标值：

def f(b, r):
    # 创建二维数组存储中间结果
    dp = [[0.0]*(r+1) for _ in range(b+1)]
    # 初始化边界条件
    for i in range(b+1):
        dp[i][0] = float(i)
    for j in range(r+1):
        dp[0][j] = 0.0
    # 填充动态规划表
    for i in range(1, b+1):
        for j in range(1, r+1):
            var = (i/(i+j)) * dp[i-1][j] + (j/(i+j)) * dp[i][j-1]
            dp[i][j] = max(i - j, var)
    return dp[b][r]

print("The solution is")
print(f(26,26))

自底向上的方式直接按依赖顺序计算所有子问题，同样避免重复计算，空间复杂度为O(b*r)，处理大输入效率同样很高。

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