Reconstructing Optimal DP Solutions — DP தீர்வு மீள்கட்டுமானம்

மதிப்பு பின் parent நடை; பாதை அச்சு.

உண்மை உலகில் இது ஏன் முக்கியம்?

LCS; திட்டத் தேர்வு.

மையக் கருத்து (மாணவர்களுக்கான விளக்கம்)

choice சேமிப்பு அல்லது மீள் கணிப்பு.

Pythonில் முயற்சி செய்வோம்

def lcs_reconstruct(a: str, b: str) -> str:
    na, nb = len(a), len(b)
    dp = [[0] * (nb + 1) for _ in range(na + 1)]
    for i in range(1, na + 1):
        for j in range(1, nb + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    i, j = na, nb
    out = []
    while i and j:
        if a[i - 1] == b[j - 1]:
            out.append(a[i - 1])
            i -= 1
            j -= 1
        elif dp[i - 1][j] > dp[i][j - 1]:
            i -= 1
        else:
            j -= 1
    return ''.join(reversed(out))


print(lcs_reconstruct('abcde', 'ace'))

அடிக்கடி நேரும் தவறுகள்

• பல தீர்வு.
• parent இழப்பு.

முக்கியச் சுருக்கக் குறிப்புகள்

• தீர்மானம் சேமி.