LeetCode #62 Unique Paths: นับทางเดินด้วย memo, DP และคณิตศาสตร์

LeetCode #62 ให้หุ่นยนต์อยู่มุมซ้ายบนของตาราง m × n เดินได้เฉพาะขวาหรือลง แล้วถามว่ามีเส้นทางถึงมุมขวาล่างกี่แบบ WHY ของโจทย์นี้คือการเห็นว่า “คำตอบของช่องหนึ่งเกิดจากคำตอบของเพื่อนบ้าน” จึงแก้ได้ทั้งแบบ dynamic programming และการเลือกตำแหน่งก้าว

นึกถึงเดินในตลาดที่ห้ามย้อน: จะมาถึงแผงหนึ่งได้จากแผงซ้ายหรือแผงบนเท่านั้น จำนวนทางเข้าจึงบวกกัน ไม่ต้องวาดเส้นทางทุกเส้นจริง ๆ

วิธี 1: Top-down recursion + memo

นิยาม paths(r,c) = paths(r-1,c) + paths(r,c-1) และจำผลของช่องที่เคยคำนวณ ใช้เวลา O(mn), memo O(mn) และ call stack O(m+n) อ่านใกล้สมการ เหมาะกับการสอนหรือโจทย์ที่ภายหลังมีช่องห้ามเดิน แต่ recursion depth เป็นข้อจำกัดเมื่อขนาดโตมาก

วิธี 2: Bottom-up DP แบบหนึ่งแถว

เริ่มทุกช่องแถวแรกเป็น 1 แล้วไล่แต่ละแถว dp[col] += dp[col-1] ค่าเดิมในช่องคือทางจากด้านบน ส่วนค่าซ้ายคือทางจากซ้าย เวลา O(mn) พื้นที่ O(n) และไม่ใช้ recursion นี่คือ best default สำหรับงานทั่วไป เพราะ invariant ตรง อ่านง่าย และต่อยอด obstacles ได้

วิธี 3: Combinatorics

ทุกเส้นทางมีทั้งหมด m+n-2 ก้าว โดยเลือกตำแหน่งก้าวลง m-1 ครั้ง จึงเป็น C(m+n-2, m-1) Python math.comb คำนวณ integer exact ใช้แนวคิดพื้นที่ O(1) และเร็วมากเมื่อ grid ไม่มีสิ่งกีดขวาง แต่ถ้ากติกาเปลี่ยนเพียงเล็กน้อย สูตรอาจใช้ไม่ได้

from functools import lru_cache
from math import comb
import unittest


def paths_memo(m: int, n: int) -> int:
    @lru_cache(maxsize=None)
    def visit(row: int, col: int) -> int:
        if row == 0 or col == 0:
            return 1
        return visit(row - 1, col) + visit(row, col - 1)
    return visit(m - 1, n - 1)


def paths_dp(m: int, n: int) -> int:
    width = min(m, n)
    height = max(m, n)
    dp = [1] * width
    for _ in range(1, height):
        for col in range(1, width):
            dp[col] += dp[col - 1]
    return dp[-1]


def paths_comb(m: int, n: int) -> int:
    return comb(m + n - 2, min(m - 1, n - 1))


class UniquePathsTests(unittest.TestCase):
    def test_examples_and_thin_grids(self):
        cases = [(3, 7, 28), (3, 2, 3), (1, 1, 1), (1, 20, 1), (10, 10, 48620)]
        for solve in (paths_memo, paths_dp, paths_comb):
            for m, n, expected in cases:
                with self.subTest(method=solve.__name__, m=m, n=n):
                    self.assertEqual(solve(m, n), expected)

    def test_methods_agree_on_small_grids(self):
        for m in range(1, 8):
            for n in range(1, 8):
                expected = paths_comb(m, n)
                self.assertEqual(paths_memo(m, n), expected)
                self.assertEqual(paths_dp(m, n), expected)


if __name__ == "__main__":
    unittest.main()

Decision table

เงื่อนไข	Memo recursion	1-row DP	Combinatorics
Input เล็ก / สอน recurrence	เห็นสูตรชัด	ชัด	ต้องรู้การจัดหมู่
Grid ใหญ่	O(mn) + stack	O(mn)	เร็วสุดสำหรับ grid โล่ง
Memory จำกัด	O(mn)	O(min(m,n))	O(1) เชิงโครงสร้าง
มี obstacle / ค่าแต่ละช่อง	ปรับง่าย	ปรับง่ายและเสถียร	ใช้สูตรตรง ๆ ไม่ได้
Streaming แถวของ obstacle	ต้องเข้าถึง state	รับทีละแถวได้	ไม่รองรับกติกานี้
ห้ามแก้ input	ไม่แตะ grid	ไม่แตะ grid	ไม่แตะ grid
Readability สำหรับทีมทั่วไป	ดีแต่มี recursion	ดีที่สุด	สั้นแต่ต้องอธิบายเหตุผล

Edge cases และ trade-offs

เมื่อมิติใดเป็น 1 มีทางเดียว; ตาราง 1×1 นับเส้นทางว่างเป็น 1 ตามโจทย์ Python ไม่มี integer overflow แต่ Java/C++ ต้องเลือกชนิดตามขอบเขต ห้ามใช้ floating-point factorial เพราะค่ากลางใหญ่และ rounding ทำให้คำตอบผิด DP หนึ่งแถวเลือกด้านสั้นเป็น width เพื่อลด memory โดยไม่เปลี่ยนคำตอบ

Recap

• เขียน recurrence จากทางเข้าซ้ายและบนก่อน
• ใช้ memo เมื่อรูปแบบ state ซับซ้อนและอยากเขียน top-down
• ใช้ one-row DP เป็น default ที่ต่อยอดง่าย
• ใช้ comb เมื่อ grid โล่งและต้องการคำตอบตรงที่สุด