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

Question

I'm trying to come up with a DP solution to Moons and Umbrellas from Code Jam's Qualification Round 2021. Below is my working recursive solution, based on their 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)}')

The problem in a nutshell is given a string of C's, J's, and ?s (e.g. CCJCJ??JC or JCCC??CJ), the question marks should be replaced by either C or J. Minimize the cost of transitioning from Cto J or vice versa. The two types of transitions have different costs.

How do I convert it to a DP solution using the bottom-up approach?

Answer 1

This solution works for all 3 Test sets:

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

I found this solution from Optidad Ranked 39 Qualification round

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())}")

For me, this is the closest thing to DP and I find the solution very clean