如何将Code Jam问题Moons and Umbrellas的递归解法转为自底向上DP

自底向上DP转换思路 #

你原有的递归解法属于带记忆化的自顶向下实现，隐式维护了「当前处理位置」和「该位置最终填C/J」两个核心状态。转换为自底向上实现只需要将这两个状态显式定义，从字符串开头向后逐位计算最小成本即可：

• 状态定义：设dp[i][0]表示处理到字符串第i位、且第i位填C时的最小总成本；dp[i][1]表示处理到第i位、且第i位填J时的最小总成本。
• 初始化：根据字符串首字符的情况给初始状态赋值，不可能出现的状态用足够大的无穷值标记。
• 状态转移：从第1位开始遍历每个字符：
  • 若当前位可填C（字符为C或?），则成本取「前一位填C的无切换成本」和「前一位填J加J转C成本Y」的最小值
  • 若当前位可填J（字符为J或?），则成本取「前一位填J的无切换成本」和「前一位填C加C转J成本X」的最小值
• 最终结果：取最后一位两种状态的最小值即可。

基础版自底向上DP实现 #

T = int(input())
# 定义足够大的无穷值，超过所有可能的总成本即可
INF = 10 ** 18
for case in range(1, T+1):
    X, Y, S = input().split()
    X = int(X)
    Y = int(Y)
    n = len(S)
    dp = [[INF] * 2 for _ in range(n)]
    # 初始化首字符状态
    if S[0] == 'C' or S[0] == '?':
        dp[0][0] = 0
    if S[0] == 'J' or S[0] == '?':
        dp[0][1] = 0
    # 逐位转移
    for i in range(1, n):
        # 计算当前位填C的最小成本
        if S[i] == 'C' or S[i] == '?':
            dp[i][0] = min(dp[i-1][0], dp[i-1][1] + Y)
        # 计算当前位填J的最小成本
        if S[i] == 'J' or S[i] == '?':
            dp[i][1] = min(dp[i-1][1], dp[i-1][0] + X)
    res = min(dp[-1][0], dp[-1][1])
    print(f'Case #{case}: {res}')

空间优化版实现 #

由于每次转移仅需要前一位的状态，不需要存储整个DP数组，可以将空间复杂度优化到O(1)：

T = int(input())
INF = 10 ** 18
for case in range(1, T+1):
    X, Y, S = input().split()
    X = int(X)
    Y = int(Y)
    # 仅存储前一位的两种状态
    prev_c, prev_j = INF, INF
    if S[0] == 'C' or S[0] == '?':
        prev_c = 0
    if S[0] == 'J' or S[0] == '?':
        prev_j = 0
    for c in S[1:]:
        curr_c, curr_j = INF, INF
        if c == 'C' or c == '?':
            curr_c = min(prev_c, prev_j + Y)
        if c == 'J' or c == '?':
            curr_j = min(prev_j, prev_c + X)
        prev_c, prev_j = curr_c, curr_j
    res = min(prev_c, prev_j)
    print(f'Case #{case}: {res}')

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