ข้อ 63 · LC62 Unique Paths (นับเส้นทางเดิน) 🟡

โจทย์ (LC62): robot (หุ่นยนต์) อยู่ที่มุมบนซ้ายของ grid (กริด) ขนาด m x n พยายามเดินไปให้ถึงมุมล่างขวาของ grid โดยแต่ละก้าวเดินได้แค่ลงหนึ่งช่องหรือขวาหนึ่งช่องเท่านั้น ให้หาว่ามี unique path (เส้นทางที่ต่างกัน) ทั้งหมดกี่แบบ

แนวทาง — ต้องใช้อะไร & คิดยังไง

เป็น 2D DP แบบ grid define (นิยาม) dp[i][j] = จำนวน path จากมุมเริ่มมาถึงช่อง (i, j) การจะมาถึงช่องนี้ได้ ก้าวสุดท้ายต้องมาจากช่องบน (i-1, j) หรือช่องซ้าย (i, j-1) เท่านั้น จำนวน path จึงเท่ากับผลบวกของสองช่องนั้น

ถ้าคิดแบบ brute force คือลองเดินทุก path ด้วย recursion (การเรียกตัวเอง) จะช้ามาก (exponential) เพราะ path ซ้ำกันเยอะ (overlapping subproblems — ปัญหาย่อยซ้ำ) การเก็บ dp[i][j] ไว้ใช้ซ้ำจึงลดเหลือ O(m·n)

1. สร้าง table dp ขนาด m x n initialize (ตั้งค่าเริ่มต้น) ทุกช่องเป็น 1
2. row บนสุด (i=0) และ column ซ้ายสุด (j=0) มีทางเดียวเสมอ (เดินตรงทิศเดียว) จึงเป็น 1 อยู่แล้ว
3. iterate i และ j จาก 1 ขึ้นไป: dp[i][j] = dp[i-1][j] + dp[i][j-1]
4. return dp[m-1][n-1] (มุมล่างขวา)

ไล่ทีละสเต็ป

table m = 3, n = 3 หลังเติมเต็ม (แต่ละช่องคือผลบวกของช่องบน + ช่องซ้าย):

def unique_paths(m, n):
    # dp[i][j] = จำนวนทางเดินมาถึงช่อง (i, j)
    dp = [[1] * n for _ in range(m)]   # แถวบนสุด/คอลัมน์ซ้ายสุด = 1 ทาง
    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, 2))  # 3

28
3