เส้นทางไม่ซ้ำและผลรวมเส้นทางต่ำสุดบนกริด

เส้นทางที่ไม่ซ้ำกันบนตาราง

# 3x7 grid: robot starts at (0,0), goes to (2,6)
# Must make exactly 2 down-moves and 6 right-moves
# Total moves = 8, choose 2 for down = C(8,2) = 28
import math
print('Unique paths 3x7:', math.comb(3+7-2, 3-1))  # 28
print('Unique paths 3x3:', math.comb(3+3-2, 3-1))  # 6
print('Unique paths 2x2:', math.comb(2+2-2, 2-1))  # 2

ตาราง DP สองมิติสำหรับเส้นทางที่ไม่ซ้ำกัน

def unique_paths(m, n):
    dp = [[1] * n for _ in range(m)]
    # First row and column stay as 1s (base cases)
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
    return dp[m-1][n-1]

print(unique_paths(3, 7))  # 28
print(unique_paths(3, 3))  # 6
print(unique_paths(1, 1))  # 1 (already at destination)

การลดหน่วยความจำเป็น O(n)

def unique_paths_1d(m, n):
    dp = [1] * n  # initial row: all 1s
    for i in range(1, m):
        for j in range(1, n):
            dp[j] += dp[j-1]  # dp[j] was dp[i-1][j], dp[j-1] is dp[i][j-1]
    return dp[n-1]

print(unique_paths_1d(3, 7))  # 28
print(unique_paths_1d(3, 3))  # 6

# Or use math for O(1)
import math
print(math.comb(3+7-2, 3-1))  # 28

เส้นทางที่ไม่ซ้ำกัน II: สิ่งกีดขวาง

def unique_paths_with_obstacles(obstacle_grid):
    m, n = len(obstacle_grid), len(obstacle_grid[0])
    dp = [[0] * n for _ in range(m)]
    # First row
    for j in range(n):
        if obstacle_grid[0][j] == 1: break
        dp[0][j] = 1
    # First column
    for i in range(m):
        if obstacle_grid[i][0] == 1: break
        dp[i][0] = 1
    for i in range(1, m):
        for j in range(1, n):
            if obstacle_grid[i][j] == 0:
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
    return dp[m-1][n-1]

grid = [[0,0,0],[0,1,0],[0,0,0]]
print(unique_paths_with_obstacles(grid))  # 2

ปัญหาผลรวมเส้นทางต่ำสุด

grid = [[1, 3, 1],
        [1, 5, 1],
        [4, 2, 1]]
# Optimal path: (0,0)→(0,1)→(0,2)→(1,2)→(2,2)
# Values:        1  +  3  +  1  +  1  +  1  = 7
print('Expected minimum path sum:', 7)

การใช้งาน DP สำหรับผลรวมเส้นทางต่ำสุด

def min_path_sum(grid):
    m, n = len(grid), len(grid[0])
    dp = [[0]*n for _ in range(m)]
    dp[0][0] = grid[0][0]
    for j in range(1, n):  # first row
        dp[0][j] = dp[0][j-1] + grid[0][j]
    for i in range(1, m):  # first column
        dp[i][0] = dp[i-1][0] + grid[i][0]
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
    return dp[m-1][n-1]

grid = [[1,3,1],[1,5,1],[4,2,1]]
print(min_path_sum(grid))  # 7

ผลรวมเส้นทางต่ำสุดในข้อมูลเดิม

def min_path_sum_inplace(grid):
    m, n = len(grid), len(grid[0])
    # Mutate in place
    for i in range(m):
        for j in range(n):
            if i == 0 and j == 0: continue
            if i == 0:
                grid[i][j] += grid[i][j-1]
            elif j == 0:
                grid[i][j] += grid[i-1][j]
            else:
                grid[i][j] += min(grid[i-1][j], grid[i][j-1])
    return grid[m-1][n-1]

import copy
grid = [[1,3,1],[1,5,1],[4,2,1]]
print(min_path_sum_inplace(copy.deepcopy(grid)))  # 7

ผลรวมเส้นทางต่ำสุดในสามเหลี่ยม

def minimum_total(triangle):
    # Bottom-up: start from second-to-last row
    dp = triangle[-1][:]  # copy of bottom row
    for row in range(len(triangle) - 2, -1, -1):
        for col in range(len(triangle[row])):
            dp[col] = triangle[row][col] + min(dp[col], dp[col+1])
    return dp[0]

triangle = [
    [2],
    [3, 4],
    [6, 5, 7],
    [4, 1, 8, 3]
]
print(minimum_total(triangle))  # 11 (2+3+5+1)

DP บนตารางของดันเจียน

def calculate_minimum_hp(dungeon):
    m, n = len(dungeon), len(dungeon[0])
    dp = [[0]*n for _ in range(m)]
    # Fill from bottom-right
    dp[m-1][n-1] = max(1, 1 - dungeon[m-1][n-1])
    for i in range(m-2, -1, -1):  # last column
        dp[i][n-1] = max(1, dp[i+1][n-1] - dungeon[i][n-1])
    for j in range(n-2, -1, -1):  # last row
        dp[m-1][j] = max(1, dp[m-1][j+1] - dungeon[m-1][j])
    for i in range(m-2, -1, -1):
        for j in range(n-2, -1, -1):
            need = min(dp[i+1][j], dp[i][j+1])
            dp[i][j] = max(1, need - dungeon[i][j])
    return dp[0][0]

dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]
print(calculate_minimum_hp(dungeon))  # 7

การเปรียบเทียบปัญหา DP บนตาราง

# Summary: Grid DP Patterns
#
# Problem          Fill Dir   Transition
# Unique Paths     top-left   dp[i][j] = dp[i-1][j] + dp[i][j-1]
# Unique Paths II  top-left   same but 0 if obstacle
# Min Path Sum     top-left   dp[i][j] = grid[i][j] + min(above, left)
# Triangle         bottom-up  dp[col] = row[col] + min(dp[col], dp[col+1])
# Dungeon          bottom-right max(1, min(right, down) - cell)

# Recognise the pattern, write the transition, verify with examples
print('Grid DP summary complete')

สรุปความซับซ้อนสำหรับ DP บนตาราง

# O(n) space version of Min Path Sum
def min_path_sum_1d(grid):
    m, n = len(grid), len(grid[0])
    dp = [float('inf')] * n
    dp[0] = 0
    for i in range(m):
        dp[0] += grid[i][0]  # first column: only from above
        for j in range(1, n):
            dp[j] = grid[i][j] + min(dp[j], dp[j-1])
    return dp[n-1]

grid = [[1,3,1],[1,5,1],[4,2,1]]
print(min_path_sum_1d(grid))  # 7

ตรวจสอบความเข้าใจ

สรุปบทเรียน