Multi-State DP (Masks, Layers, Digit DP) — பல-நிலை DP

பல நிலை — mask; digit DP tight.

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

சாவி maze; வரி எண்.

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

சிறு enum விரிவு.

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

def multi_state_paths(n: int, m: int) -> int:
    # count paths with at most one diagonal hop (toy)
    dp = [[[0, 0] for _ in range(m)] for _ in range(n)]
    dp[0][0][0] = 1
    for i in range(n):
        for j in range(m):
            for used in range(2):
                v = dp[i][j][used]
                if not v:
                    continue
                if i + 1 < n:
                    dp[i + 1][j][used] += v
                if j + 1 < m:
                    dp[i][j + 1][used] += v
                if i + 1 < n and j + 1 < m and used == 0:
                    dp[i + 1][j + 1][1] += v
    return sum(dp[-1][-1])


print(multi_state_paths(3, 3))

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

• பெரிய mask.
• கொடி மீட்டமைப்பு.

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

• சமச்சீர் குறைப்பு.