Recursion Pruning — அடிப்படை

சுயமுறை கத்தரிப்பு — இதுவரை சிறந்த பதிலை விட மேம்பட முடியாது எனில் return.

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

கிளை-வரம்பு; ஆட்ட மரம் வெட்டு.

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

best_so_far பகிர்வு; எல்லை ஒப்பீடு.

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

def min_path_sum(grid: list[list[int]]) -> int:
    m, n = len(grid), len(grid[0])
    big = 10**18
    dp = [[big] * n for _ in range(m)]
    dp[0][0] = grid[0][0]
    for i in range(m):
        for j in range(n):
            if i:
                dp[i][j] = min(dp[i][j], dp[i - 1][j] + grid[i][j])
            if j:
                dp[i][j] = min(dp[i][j], dp[i][j - 1] + grid[i][j])
    return dp[-1][-1]


print(min_path_sum([[1, 3, 1], [1, 5, 1], [4, 2, 1]]))

பொதுவான தவறுகள்

• அனுமதியற்ற எல்லை.
• float.

முக்கிய பாடங்கள்

• admissible நிரூபணம்.
• monotonic.