代码之家 › 专栏 › 技术社区 › planetp

如何将“月亮和雨伞”的递归解决方案转换为DP?

memoization dynamic-programming recursion algorithm python

planetp · 技术社区 · 3 年前

我正试图想出一个DP解决方案 Moons and Umbrellas 来自2021年Code Jam资格赛。以下是我的工作递归解决方案,基于它们 analysis :

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 s J 的,以及 ? s(例如。 CCJCJ??JC 或 JCCC??CJ ),问号应替换为 C 或 J .最大限度地降低从 C 到 J 反之亦然。这两种类型的转换具有不同的成本。

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

1 回复 | 直到 3 年前

planetp 3 年前

此解决方案适用于所有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])}')

Raphael Obadia 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的东西,我发现解决方案非常干净