如何将"Moons and Umbrellas"的递归解转化为DP？

Question

我正在尝试为 Moons and Umbrellas from Code Jam's Qualification Round 2021. Below is my working recursive solution, based on their analysis 提出一个 DP 解决方案：

import sys
from functools import lru_cache

sys.setrecursionlimit(5000)

T = int(input())

for case in range(1, T+1):
    X, Y, S = input().split()
    X = int(X)
    Y = int(Y)
    S = tuple(S)

    @lru_cache(maxsize=128)
    def cost(S):
        if len(S) <= 1:
            return 0

        if S[0] == '?':
            return min(cost(('C',) + S[1:]), cost(('J',) + S[1:]))

        if S[0] != '?' and S[1] == '?':
            return min(cost((S[0],) + ('C',) + S[2:]), cost((S[0],) + ('J',) + S[2:]))

        if S[0] == S[1]:
            return cost(S[1:])

        if S[0] == 'C' and S[1] == 'J':
            return X + cost(S[1:])

        if S[0] == 'J' and S[1] == 'C':
            return Y + cost(S[1:])

    print(f'Case #{case}: {cost(S)}')

简而言之，给出的问题是 C、J 和 ? 的字符串（例如 CCJCJ??JC 或 JCCC??CJ)，问号应替换为 C 或 J。最小化从 C 到 J 的转换成本，反之亦然。两种类型的转换具有不同的成本。

如何使用自下而上的方法将其转换为 DP 解决方案？

Answer 1

此解决方案适用于所有 3 个测试集：

T = int(input())

C, J = 0, 1
INF = float('inf')

for case in range(1, T+1):
    X, Y, S = input().split()
    X = int(X)  # CJ
    Y = int(Y)  # JC

    dp = [[None, None] for _ in range(len(S))]

    for i, c in enumerate(S):
        if i == 0:
            if c == 'C':
                dp[i][C] = 0
                dp[i][J] = INF
            elif c == 'J':
                dp[i][J] = 0
                dp[i][C] = INF
            elif c == '?':
                dp[i][C] = 0
                dp[i][J] = 0
        else:
            if c == 'C':
                dp[i][J] = INF
                if S[i-1] == 'C':
                    dp[i][C] = dp[i-1][C]
                elif S[i-1] == 'J':
                    dp[i][C] = dp[i-1][J] + Y
                elif S[i-1] == '?':
                    dp[i][C] = min(dp[i-1][C], dp[i-1][J] + Y)
            elif c == 'J':
                dp[i][C] = INF
                if S[i-1] == 'C':
                    dp[i][J] = dp[i-1][C] + X
                elif S[i-1] == 'J':
                    dp[i][J] = dp[i-1][J]
                elif S[i-1] == '?':
                    dp[i][J] = min(dp[i-1][J], dp[i-1][C] + X)
            elif c == '?':
                if S[i-1] == 'C':
                    dp[i][C] = dp[i-1][C]
                    dp[i][J] = dp[i-1][C] + X
                elif S[i-1] == 'J':
                    dp[i][C] = dp[i-1][J] + Y
                    dp[i][J] = dp[i-1][J]
                elif S[i-1] == '?':
                    dp[i][C] = min(dp[i-1][C], dp[i-1][J] + Y)
                    dp[i][J] = min(dp[i-1][J], dp[i-1][C] + X)

    print(f'Case #{case}: {min(dp[-1])}')

Answer 2

我从 Optidad 排名第 39 的资格赛中找到了这个解决方案

t = int(input())
for case in range(t):
    cj, xj, s = input().split()
    N = len(s)
    last = {"X": 0}

    for i in range(N):

        next_last = {}
        for a, v in last.items():
            if s[i] != "C":  # J or ?
                next_last["J"] = min(v + int(cj) * int(a == "C"), next_last.get("J", 9999999))
            if s[i] != "J":  # C or ?
                next_last["C"] = min(v + int(xj) * int(a == "J"), next_last.get("C", 9999999))
        last = dict(next_last)
    print(f"Case #{case + 1}: {min(last.values())}")

对我来说，这是最接近 DP 的东西，我发现解决方案非常干净

如何将"Moons and Umbrellas"的递归解转化为DP？

How to convert the recursive solution to "Moons and Umbrellas" to DP?

python

algorithm

recursion

dynamic-programming

bottom-up