แนะนำการโปรแกรมเชิงพลวัตและกราฟ (เชิงแนวคิด)

วันนี้เราจะพบกับสองแนวคิดใหญ่: การโปรแกรมเชิงพลวัต (Dynamic Programming) คือการ “จำ” คำตอบของปัญหาย่อยไว้ใช้ซ้ำ และ กราฟ (Graphs) คือการสร้างแบบจำลองของความสัมพันธ์ระหว่างสิ่งต่าง ๆ ทั้งสองเรื่องมีสูตรสำเร็จเยอะ โจทย์คลาสสิกซ้ำ ๆ กันเรื่อยตั้งแต่หนังสือเรียนจนถึงห้องสัมภาษณ์งาน — คำเตือนสำคัญ: นี่คือหัวข้อที่ AI ให้คำตอบ “ดูเหมือนถูก แต่ผิดแบบแอบแฝง” บ่อยที่สุด เพราะโค้ดที่มี recurrence ผิดนิดเดียว หรือกราฟที่ลืม visited set ยังคง รันได้และให้คำตอบดูสมเหตุสมผล กับตัวอย่างเล็ก ๆ เสมอ ดังนั้นต้องตรวจสอบเสมอ ไม่ใช่แค่ “รันผ่านก็พอ”

Dynamic Programming

ลองนึกภาพว่าคุณกำลังทำโจทย์เลขที่ซับซ้อน แล้วจดผลลัพธ์ย่อยที่คำนวณแล้วไว้ในกระดาษทด — ถ้าเจอโจทย์ย่อยเดิมอีกครั้งระหว่างทาง คุณแค่มองกระดาษทดแทนที่จะคำนวณใหม่ทั้งหมด นี่คือหัวใจของ การโปรแกรมเชิงพลวัต (DP): เทคนิคแก้ปัญหาด้วยการแตกปัญหาใหญ่เป็นปัญหาย่อย แล้ว จำคำตอบ ของปัญหาย่อยเอาไว้ เพื่อไม่ต้องคำนวณซ้ำ

ปัญหาจะเหมาะกับ DP เมื่อมีสองคุณสมบัติต่อไปนี้ครบทั้งคู่:

Overlapping subproblems (ปัญหาย่อยซ้อนทับกัน) — ปัญหาย่อยเดิม ๆ ถูกคำนวณซ้ำหลายครั้งถ้าแก้แบบ recursion ตรง ๆ

Optimal substructure (โครงสร้างย่อยที่เหมาะที่สุด) — คำตอบที่ดีที่สุดของปัญหาใหญ่ ประกอบขึ้นจากคำตอบที่ดีที่สุดของปัญหาย่อย

ถ้าขาดคุณสมบัติข้อใดข้อหนึ่ง DP อาจช่วยไม่ได้เต็มที่: มีแค่ overlapping subproblems อย่างเดียวไม่พอ (ต้องพิสูจน์ว่าคำตอบย่อยประกอบกันเป็นคำตอบใหญ่ที่ดีที่สุดได้จริง) และมีแค่ optimal substructure อย่างเดียวก็ยังไม่คุ้มจะ cache (เช่น divide-and-conquer แบบ merge sort ที่ปัญหาย่อยไม่ซ้ำกันเลย)

Top-down (Memoization) vs Bottom-up (Tabulation)

มีสองวิธีหลักในการเขียน DP:

• Memoization (top-down) — เขียนแบบเรียกตัวเอง (recursion) ตามธรรมชาติที่สุด แล้วเก็บผลลัพธ์ลง cache เมื่อเจอปัญหาย่อยซ้ำก็ดึงจาก cache แทนการคำนวณใหม่
• Tabulation (bottom-up) — สร้างตาราง แล้วเติมคำตอบจากปัญหาย่อยที่เล็กที่สุดไล่ขึ้นไปจนถึงปัญหาใหญ่ ไม่ใช้ recursion เลย

หัวข้อ	Top-down (Memoization)	Bottom-up (Tabulation)
เขียนยังไง	recursion ธรรมชาติ + cache	ลูป (for/while) เติมตารางไล่ลำดับ
คำนวณปัญหาย่อยไหนบ้าง	เฉพาะที่ถูกเรียกใช้จริง	ทุกปัญหาย่อยตามลำดับที่กำหนด
เสี่ยง stack overflow ไหม	เสี่ยง ถ้า n ใหญ่มาก (ชนขีดจำกัด recursion ของ Python)	ไม่เสี่ยง เพราะไม่มี recursion
เขียนง่ายที่สุดจาก	สมการเวียนเกิด (recurrence) ตรง ๆ	ต้องคิดลำดับการเติมตารางเอง
ปรับหน่วยความจำภายหลัง	ทำยาก (โครงสร้าง cache ผูกกับ recursion)	ทำง่าย (ลด array มิติเดียวได้บ่อยครั้ง เช่น rolling array)

ข้อคิดสำคัญ: DP ไม่ใช่อัลกอริทึมชนิดหนึ่ง แต่คือ “การจำ” — ถ้าเจอ recursion ที่คำนวณค่าเดิมซ้ำ ๆ ให้สงสัยไว้ก่อนว่าใส่ memo หรือ tabulation ได้

ตัวอย่างประกอบ: Fibonacci

ลำดับ Fibonacci คือ F(0)=0, F(1)=1, และ F(n) = F(n-1) + F(n-2)

เขียนแบบ recursion ตรง ๆ จะได้โค้ดที่สวยงาม แต่ ช้ามาก:

def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

โค้ดนี้มีความซับซ้อน O(2ⁿ) เพราะ call-tree แตกออกเป็นสองกิ่งในทุกชั้น และคำนวณค่าเดิมซ้ำมหาศาล เช่น fib(5) จะเรียก fib(3) สองครั้ง, fib(2) สามครั้ง เป็นต้น

ลองเลื่อน slider ในวิดเจ็ตข้างบนดูว่า call-tree แตกกิ่งเร็วแค่ไหน — และสังเกตว่าโหนดสีซ้ำ (ปัญหาย่อยเดิม) โผล่ขึ้นมาบ่อยแค่ไหนเมื่อ n โต ตัวเลขจริงยิ่งน่ากลัวกว่า:

n	จำนวนครั้งที่ฟังก์ชันถูกเรียก (ประมาณ)	เวลาที่ใช้ (โดยประมาณ*)
10	~177	เร็วจนไม่รู้สึก
20	~21,891	เสี้ยววินาที
30	~2,692,537	~1 วินาที
40	~331,160,281	หลายนาที
50	~4 × 10¹⁰	หลายชั่วโมงถึงหลายวัน

*เวลาจริงขึ้นกับเครื่อง ประเด็นคือรูปแบบการเติบโตเป็น exponential — เพิ่ม n ทีละ 10 เวลาพุ่งขึ้นหลายพันเท่า

แก้ด้วย memoization เก็บผลลัพธ์ที่เคยคำนวณ:

def fib(n, memo={}):
    if n < 2:
        return n
    if n in memo:
        return memo[n]
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
    return memo[n]

หรือใช้ functools.lru_cache ให้สั้นลง:

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

ทั้งสองแบบลดความซับซ้อนเหลือ O(n) เพราะแต่ละค่า fib(k) ถูกคำนวณจริงเพียงครั้งเดียว ครั้งถัดไปดึงจาก cache ทันที call-tree ที่เคยแตกเป็นพุ่มจึงยุบเหลือเป็นเส้นตรง — นี่คือหัวใจของ DP

ระวัง: def fib(n, memo={}) ใช้ mutable default argument ซึ่งใน Python ค่า default จะถูกสร้างครั้งเดียวตอนนิยามฟังก์ชัน ไม่ใช่ทุกครั้งที่เรียก ปกติเป็นแอนตี้แพทเทิร์นอันตราย แต่ในเคสนี้เราตั้งใจใช้ประโยชน์จากมันเพื่อให้ cache อยู่ข้ามการเรียกฟังก์ชัน — ถ้าไม่ตั้งใจแบบนี้ ให้ใช้ lru_cache แทนจะปลอดภัยกว่า (ดูแบบฝึกหัดข้อ 2)

ตัวอย่างประกอบ: Unique Paths (ตาราง DP สองมิติ)

โจทย์: หุ่นยนต์อยู่มุมซ้ายบนของตารางขนาด m × n เดินได้แค่ ขวา หรือ ลง ทีละช่อง มีกี่เส้นทางที่ไปถึงมุมขวาล่างได้

สมการเวียนเกิด: การจะมาถึงช่อง (i, j) ได้ ต้องมาจากช่องบน (i-1, j) หรือช่องซ้าย (i, j-1) เท่านั้น

dp[i][j] = dp[i-1][j] + dp[i][j-1]
dp[0][j] = 1   (แถวบนสุด เดินตรงมาทางเดียว)
dp[i][0] = 1   (คอลัมน์ซ้ายสุด เดินตรงมาทางเดียว)

นี่คือ bottom-up tabulation ตัวอย่างที่ชัดเจนมาก: เราเติมตารางจากช่องเล็ก ๆ (แถว/คอลัมน์แรก) ไล่ไปจนถึงช่องเป้าหมาย โดยไม่ใช้ recursion เลย

ลองดูวิดเจ็ตข้างบนเติมตารางทีละช่อง สำหรับตาราง 4 แถว × 5 คอลัมน์ ค่าสุดท้ายจะได้:

	col 0	col 1	col 2	col 3	col 4
row 0	1	1	1	1	1
row 1	1	2	3	4	5
row 2	1	3	6	10	15
row 3	1	4	10	20	35

คำตอบคือช่องขวาล่างสุด: 35 เส้นทาง

def unique_paths(m: int, n: int) -> int:
    dp = [[1] * n for _ in range(m)]
    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]

ความซับซ้อน: O(m·n) ทั้งเวลาและหน่วยความจำ เพราะเราเติมทุกช่องในตารางเพียงครั้งเดียว (ดูแบบฝึกหัดข้อท้าย ๆ ว่าจะลดหน่วยความจำเหลือ O(n) ได้อย่างไร)

ตัวอย่างประกอบ: Coin Change (จำนวนเหรียญน้อยที่สุด)

โจทย์: มีเหรียญชนิดต่าง ๆ coins = [1, 2, 5] ต้องการทอนเงินจำนวน amount = 11 ด้วยจำนวนเหรียญน้อยที่สุด ใช้เหรียญกี่เหรียญ

สมการเวียนเกิด: ถ้าจะทอนเงินจำนวน a ให้ลองทุกเหรียญ c ที่ c ≤ a แล้วดูว่าทอน a - c (ที่เหลือ) ใช้กี่เหรียญ บวกอีกหนึ่งเหรียญที่เพิ่งใช้ — เลือกทางที่น้อยที่สุด

dp[0] = 0
dp[a] = min(dp[a - c] + 1)  สำหรับทุกเหรียญ c ที่ c ≤ a

ตารางไล่ตั้งแต่ amount = 0 ถึง 11 (coins = [1, 2, 5]):

amount	0	1	2	3	4	5	6	7	8	9	10	11
dp[amount]	0	1	1	2	2	1	2	2	3	3	2	3

เช่น dp[11] = 3 เพราะ 11 = 5 + 5 + 1 (3 เหรียญ) ซึ่งดีกว่าการโลภใช้เหรียญใหญ่สุดก่อนเสมอ (ดูหัวข้อ AI Code Critique ด้านล่าง ว่าทำไม “โลภ” ถึงพังกับเหรียญบางชุด)

def coin_change(coins: list[int], amount: int) -> int:
    dp = [0] + [float("inf")] * amount
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a:
                dp[a] = min(dp[a], dp[a - c] + 1)
    return dp[amount] if dp[amount] != float("inf") else -1

ความซับซ้อน: O(amount × len(coins)) เวลา, O(amount) หน่วยความจำ จุดที่ AI มักพลาด: ลืม -1 เมื่อทอนไม่ได้ (เช่น coins = [5], amount = 3) — ถ้าไม่เช็ค float("inf") ตอนจบ จะคืนค่า inf แปลก ๆ ออกไปแทน

Graphs

ถ้า DP คือการ “จำคำตอบปัญหาย่อย” กราฟก็คือการ “สร้างแบบจำลอง” ความสัมพันธ์ระหว่างสิ่งต่าง ๆ ให้เป็นรูปทรงที่คอมพิวเตอร์เข้าใจ — เพื่อนบนโซเชียล, ถนนระหว่างเมือง, ลิงก์ระหว่างเว็บเพจ, งานที่ต้องทำก่อนงานอื่น (dependency) ล้วนเป็น “โหนดที่เชื่อมกัน” ทั้งสิ้น

กราฟคือโครงสร้างข้อมูลที่ประกอบด้วย โหนด (nodes / vertices) และ เส้นเชื่อม (edges) ที่บอกความสัมพันธ์ระหว่างโหนด

• Directed (มีทิศทาง) — เส้นเชื่อมไปทางเดียว เช่น A → B (เช่น การ follow บนโซเชียล)
• Undirected (ไม่มีทิศทาง) — เส้นเชื่อมไปทั้งสองทาง เช่น A — B (เช่น การเป็นเพื่อนกัน)

Adjacency List vs Adjacency Matrix

วิธีเก็บกราฟในหน่วยความจำมีสองแบบหลัก และการเลือกผิดคือจุดที่ทำให้โปรแกรมช้าหรือกินแรมเกินจำเป็นบ่อยที่สุด:

	Adjacency List	Adjacency Matrix
โครงสร้าง	แต่ละโหนดเก็บ list ของเพื่อนบ้าน	ตาราง 2 มิติขนาด V × V
หน่วยความจำ	O(V + E) — ประหยัดเมื่อกราฟเบาบาง (sparse)	O(V²) เสมอ ไม่ว่าเส้นเชื่อมจะเยอะหรือน้อย
เช็คว่า A-B เชื่อมกันไหม	O(deg(A)) — ต้องไล่ list	O(1) — เปิดช่อง [A][B] ได้ทันที
ไล่เพื่อนบ้านทั้งหมดของโหนดหนึ่ง	O(deg(v)) — เร็ว เพราะมีแค่เพื่อนบ้านจริง	O(V) — ต้องไล่ทั้งแถวแม้เพื่อนบ้านมีน้อย
เหมาะกับ	กราฟเบาบาง (ถนน, โซเชียล, dependency graph) — ส่วนใหญ่ในชีวิตจริง	กราฟหนาแน่น (dense) หรือกราฟเล็กที่ต้องเช็คการเชื่อมบ่อยมาก

กฎง่าย ๆ: กราฟในโลกจริงมักเบาบาง (E ใกล้เคียง V มากกว่า V²) — เมื่อไม่แน่ใจ ให้เริ่มจาก adjacency list ก่อนเสมอ

BFS vs DFS

ทั้งสองคือวิธีเดินสำรวจกราฟ (graph traversal) แต่ลำดับการสำรวจต่างกันโดยสิ้นเชิง:

• BFS (Breadth-First Search) — สำรวจ “แผ่กว้าง” ทีละชั้นจากจุดเริ่มต้น เยี่ยมเพื่อนบ้านทั้งหมดก่อนแล้วค่อยลงลึก ใช้ queue
• DFS (Depth-First Search) — สำรวจ “ลงลึก” ไปตามกิ่งหนึ่งจนสุดก่อน แล้วค่อยถอยกลับ (backtrack) ใช้ stack (หรือ recursion ซึ่งก็คือ stack ที่ระบบจัดการให้)

ลองสั่งให้วิดเจ็ตข้างบนรันทั้ง BFS และ DFS บนกราฟเดียวกัน แล้วสังเกตว่าลำดับการเยี่ยมโหนดต่างกันอย่างไร

	BFS	DFS
โครงสร้างข้อมูล	Queue (FIFO)	Stack (LIFO) หรือ recursion
ลำดับการสำรวจ	ทีละชั้น (level by level)	ลงลึกสุดก่อนค่อยถอย
หาเส้นทางสั้นที่สุด (unweighted)	ได้แน่นอน — โหนดที่เจอครั้งแรกอยู่ใกล้ที่สุดเสมอ	ไม่รับประกัน — อาจเจอทางอ้อมก่อน
หน่วยความจำกรณีแย่สุด	เก็บทั้งชั้น (อาจกว้างมากถ้ากราฟแตกแขนงเยอะ)	เก็บแค่เส้นทางลึกสุด (มักประหยัดกว่าในกราฟกว้าง)
ใช้เมื่อไหร่	เส้นทางสั้นที่สุด, ค้นหาระดับความสัมพันธ์ (เช่น “เพื่อนของเพื่อน”), web crawler ทีละชั้น	ตรวจ cycle, topological sort, นับ connected components, ปัญหา backtracking (เขาวงกต, sudoku)

จุดสำคัญ: BFS ให้เส้นทางสั้นที่สุดในกราฟไม่มีน้ำหนัก (unweighted) เพราะมันแผ่ออกทีละชั้น โหนดที่เจอครั้งแรกย่อมอยู่ใกล้ที่สุด ทั้ง BFS และ DFS มีความซับซ้อน O(V + E) เท่ากัน — ต่างกันแค่ “ลำดับ” ไม่ใช่ “ความเร็ว”

ตัวอย่าง BFS ด้วย queue:

from collections import deque

def bfs(graph, start):
    visited = {start}
    queue = deque([start])
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return order

ตัวอย่าง DFS แบบ recursion (สั้น อ่านง่าย แต่เสี่ยง stack overflow ถ้ากราฟลึกมาก):

def dfs_recursive(graph, node, visited=None, order=None):
    if visited is None:
        visited, order = set(), []
    visited.add(node)
    order.append(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited, order)
    return order

ตัวอย่าง DFS แบบ iterative ด้วย stack ตรง ๆ (ไม่เสี่ยง recursion limit):

def dfs_iterative(graph, start):
    visited = {start}
    stack = [start]
    order = []
    while stack:
        node = stack.pop()
        order.append(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                stack.append(neighbor)
    return order

ข้อคิดสำคัญ: BFS กับ DFS ใช้โค้ดโครงเดียวกันเป๊ะ ต่างกันแค่ queue.popleft() (BFS) กับ stack.pop() (DFS) — แต่ผลลัพธ์คนละเรื่องเลย จำตรงนี้ไว้จะช่วยไม่งงว่าอันไหนคืออันไหน

คำเตือน: AI มักสร้างโค้ด DP และกราฟที่ “ดูถูกต้อง แต่ผิดแบบแอบแฝง” — เช่น เขียนสมการเวียนเกิด (recurrence) ผิด, ลืม base case, หรือ ลืมใส่ visited set จนเกิด infinite loop เมื่อกราฟมีวงจร (cycle) ทั้งหมดนี้คอมไพล์ผ่านและรันได้กับตัวอย่างเล็ก ๆ แต่พังเงียบ ๆ กับข้อมูลจริง อย่าเชื่อโค้ดที่ AI ให้มาทันที — ต้องทดสอบและตรวจสอบเสมอ

ปัญหาจากโลกจริง

ปัญหา: เส้นทางสั้นที่สุดในตาราง (grid) ด้วย BFS

มีตาราง grid โดย 0 คือเดินได้ และ 1 คือกำแพง เริ่มที่มุมซ้ายบน (0,0) ต้องการไปมุมขวาล่าง หาจำนวนก้าวที่น้อยที่สุด — โจทย์แบบนี้คือหัวใจของเกม pathfinding, ระบบนำทางในคลังสินค้า, หรือแม้แต่การจัดเส้นทางหุ่นยนต์ดูดฝุ่น

เราจำลองช่องแต่ละช่องเป็นโหนด และช่องที่อยู่ติดกัน (บน/ล่าง/ซ้าย/ขวา) เป็น edge แล้วใช้ BFS เพราะแต่ละก้าวมี “น้ำหนัก” เท่ากัน — BFS จึงให้คำตอบเส้นทางสั้นที่สุด DFS ก็หาเส้นทางเจอเหมือนกัน แต่ไม่รับประกันว่าสั้นที่สุด

from collections import deque

def shortest_path(grid):
    rows, cols = len(grid), len(grid[0])
    start, goal = (0, 0), (rows - 1, cols - 1)
    if grid[0][0] == 1 or grid[goal[0]][goal[1]] == 1:
        return -1
    queue = deque([(start, 1)])          # (ตำแหน่ง, จำนวนก้าว)
    visited = {start}
    while queue:
        (r, c), dist = queue.popleft()
        if (r, c) == goal:
            return dist
        for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols \
               and grid[nr][nc] == 0 and (nr, nc) not in visited:
                visited.add((nr, nc))
                queue.append(((nr, nc), dist + 1))
    return -1                            # ไปไม่ถึง

visited ป้องกันการวนกลับไปช่องเดิม ทำให้ความซับซ้อนอยู่ที่ O(V + E) โดย V คือจำนวนช่อง ถ้าลืม visited ตรงนี้ โปรแกรมจะวนไปมาระหว่างช่องข้างเคียงไม่รู้จบ — เหมือนกับบั๊กที่เห็นในหัวข้อ AI Code Critique ด้านล่าง

แบบฝึกหัด

1. Big-O เบื้องต้น — coin change แบบ recursion ตรง ๆ ไม่มี memo มีความซับซ้อนเวลาเท่าไหร่ (ประมาณ) เทียบกับแบบ tabulation ที่เห็นด้านบน

เฉลย

แบบ recursion ตรง ๆ ไม่มี memo: แต่ละ a แตกกิ่งได้สูงสุด len(coins) ทาง และลึกได้ถึง amount ชั้น ทำให้เป็น O(len(coins)^amount) — exponential เหมือน fib naive แบบ tabulation ด้านบนคือ O(amount × len(coins)) เพราะแต่ละ dp[a] คำนวณจริงแค่ครั้งเดียว นี่คือเหตุผลที่ DP เปลี่ยนปัญหา exponential ให้กลายเป็น polynomial

2. Predict the output — โค้ดนี้จะพิมพ์อะไร และทำไม

def fib(n, memo={}):
    if n < 2:
        return n
    if n in memo:
        return memo[n]
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
    return memo[n]

print(fib(5))
print(len(fib.__defaults__[0]))
print(fib(3))

เฉลย

พิมพ์ 5, แล้ว 4 (เพราะ memo เก็บ {2:1, 3:2, 4:3, 5:5} ค้างอยู่จากการเรียกครั้งแรก — mutable default argument ถูกสร้างครั้งเดียวตอนนิยามฟังก์ชัน ไม่ใช่ทุกครั้งที่เรียก) แล้ว 2 (ดึงจาก cache ที่ค้างอยู่ ไม่คำนวณใหม่) — เคสนี้ใช้ผลข้างเคียงของ mutable default โดยตั้งใจเพื่อให้ cache อยู่ข้ามการเรียก แต่ในโค้ดทั่วไป การพึ่งพา mutable default โดยไม่ตั้งใจคือบั๊กคลาสสิก เพราะ state จะรั่วไหลข้ามการเรียกฟังก์ชันโดยไม่คาดคิด ทางที่ปลอดภัยกว่าคือใช้ @lru_cache หรือส่ง memo=None แล้วสร้างใหม่ข้างในถ้าเป็น None

3. Memoize ฟังก์ชันช้า — ฟังก์ชัน grid_paths(m, n) นับจำนวนเส้นทางจากมุมซ้ายบนไปมุมขวาล่าง (เดินได้แค่ขวา/ลง) เขียนแบบ recursion ก่อน แล้วเพิ่ม memoization

เฉลย

from functools import lru_cache

@lru_cache(maxsize=None)
def grid_paths(m, n):
    if m == 1 or n == 1:
        return 1
    return grid_paths(m - 1, n) + grid_paths(m, n - 1)

ไม่มี memo: O(2^(m+n)) เพราะแตกกิ่งซ้ำ มี memo: O(m·n) เพราะแต่ละคู่ (m, n) คำนวณครั้งเดียว

4. Climbing stairs — บันได n ขั้น ก้าวได้ครั้งละ 1 หรือ 2 ขั้น มีกี่วิธีในการขึ้นถึงยอด

เฉลย

นี่คือ Fibonacci แฝงตัว: วิธีขึ้นถึงขั้น n = วิธีขึ้นถึงขั้น n-1 (ก้าว 1) + วิธีขึ้นถึงขั้น n-2 (ก้าว 2)

def climb(n):
    a, b = 1, 1          # วิธีขึ้นถึงขั้น 0 และ 1
    for _ in range(n):
        a, b = b, a + b
    return a

5. Spot the bug — โค้ด coin change นี้พังตรงไหน (ลองรันด้วย coins=[2], amount=3)

def coin_change(coins, amount):
    dp = [0] * (amount + 1)
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a:
                dp[a] = min(dp[a], dp[a - c] + 1)
    return dp[amount]

เฉลย

บั๊ก: เริ่ม dp ด้วย 0 แทนที่จะเป็น float("inf") เมื่อทอนเงินไม่ได้ (เช่น coins=[2], amount=3 — เลขคี่ทอนด้วยเหรียญ 2 ไม่ได้เลย) ค่า dp[a] ที่ไม่เคยถูกอัปเดตจะยังเป็น 0 และ min(dp[a], dp[a-c]+1) จะเลือก 0 เสมอเพราะน้อยกว่าอะไรก็ตาม ผลคือฟังก์ชันคืนค่า 0 (ดูเหมือนทอนได้ 0 เหรียญ!) แทนที่จะบอกว่าทอนไม่ได้

แก้ไข: เริ่มด้วย dp = [0] + [float("inf")] * amount แล้วเช็คตอนจบว่า dp[amount] ยังเป็น inf อยู่หรือไม่ ถ้าใช่ให้คืน -1

6. เลือกโครงสร้างข้อมูลให้ถูก — คุณมีกราฟโซเชียลมีเดีย ~10 ล้านคน แต่ละคนมีเพื่อนเฉลี่ย ~200 คน คุณต้องเช็คบ่อย ๆ ว่า “A กับ B เป็นเพื่อนกันไหม” ควรเก็บกราฟนี้แบบ adjacency list หรือ adjacency matrix

เฉลย

Adjacency list เพราะกราฟนี้ เบาบาง (sparse) อย่างมาก: V = 10,000,000 แต่ E ≈ V × 200 / 2 = 1,000,000,000 ซึ่งเล็กกว่า V² = 10^14 มหาศาล ถ้าใช้ adjacency matrix จะต้องเก็บ 10^14 ช่อง — เกินหน่วยความจำของเครื่องทุกเครื่องบนโลก แม้ adjacency matrix จะเช็คการเชื่อม O(1) แต่ adjacency list ใช้ hash set สำหรับ list เพื่อนบ้านของแต่ละคนก็เช็คได้เร็วใกล้เคียง O(1) เฉลี่ย โดยใช้พื้นที่แค่ O(V + E)

7. Count graph components — ให้กราฟไม่มีทิศทาง นับจำนวนกลุ่มที่เชื่อมต่อกัน (connected components)

เฉลย

def count_components(graph, n):
    visited = set()
    count = 0
    for node in range(n):
        if node not in visited:
            count += 1
            stack = [node]                 # DFS
            while stack:
                cur = stack.pop()
                if cur in visited:
                    continue
                visited.add(cur)
                stack.extend(graph[cur])
    return count

ใช้ DFS (หรือ BFS ก็ได้ผลเหมือนกัน — ในโจทย์นี้ลำดับการเยี่ยมไม่สำคัญ) ไล่ทุกโหนดที่ยังไม่ถูกเยี่ยม แต่ละครั้งที่เจอโหนดใหม่คือเจอกลุ่มใหม่ แล้วสำรวจทั้งกลุ่มให้หมดก่อนนับกลุ่มถัดไป

8. BFS shortest path — ในกราฟไม่มีน้ำหนัก หาจำนวน edge ที่น้อยที่สุดระหว่างโหนด start กับ target

เฉลย

from collections import deque

def shortest(graph, start, target):
    if start == target:
        return 0
    visited = {start}
    queue = deque([(start, 0)])
    while queue:
        node, dist = queue.popleft()
        for nxt in graph[node]:
            if nxt == target:
                return dist + 1
            if nxt not in visited:
                visited.add(nxt)
                queue.append((nxt, dist + 1))
    return -1

ต้องใช้ BFS ไม่ใช่ DFS เพราะ DFS อาจเจอ target ผ่านทางอ้อมที่ยาวกว่าก่อน แล้วคืนค่าที่ผิด

9. Improve this code — unique_paths ด้านบนใช้หน่วยความจำ O(m·n) เพราะเก็บทั้งตาราง 2 มิติ ทั้งที่การเติมแต่ละแถวใช้แค่ “แถวก่อนหน้า” เท่านั้น ปรับโค้ดให้ใช้หน่วยความจำเหลือ O(n) โดยใช้ rolling array (แถวเดียว)

เฉลย

def unique_paths(m: int, n: int) -> int:
    row = [1] * n
    for _ in range(1, m):
        for j in range(1, n):
            row[j] += row[j - 1]   # row[j] เดิม = ค่าจากแถวก่อนหน้า (บน)
    return row[-1]

เพราะ dp[i][j] = dp[i-1][j] + dp[i][j-1] ต้องการแค่ค่าจาก “แถวบน ช่องเดียวกัน” กับ “แถวเดียวกัน ช่องซ้าย” เราจึงรีไซเคิล array เส้นเดียวได้ ก่อนอัปเดต row[j] ค่าที่อยู่ในนั้นคือ dp[i-1][j] (แถวบน) พอบวก row[j-1] (ซึ่งอัปเดตเป็นแถวปัจจุบันไปแล้ว) ก็ได้ dp[i][j] พอดี หลักการนี้ใช้ลดหน่วยความจำ DP ได้กับโจทย์ DP สองมิติจำนวนมาก

AI Code Critique

กรณีที่ 1: DP — เมื่อ “โลภมาก” ดูเหมือนถูก แต่ผิด

มีคนขอให้ AI เขียนฟังก์ชันทอนเหรียญให้น้อยที่สุด และได้โค้ดนี้กลับมา:

def coin_change(coins, amount):
    coins.sort(reverse=True)
    count = 0
    for c in coins:
        while amount >= c:
            amount -= c
            count += 1
    return count if amount == 0 else -1

โค้ดนี้คือ greedy (โลภ): หยิบเหรียญใหญ่สุดก่อนเสมอ มันรันผ่านกับ coins=[1,5,10,25] (เหรียญสหรัฐ) ได้คำตอบถูกต้องทุกครั้ง เพราะบังเอิญเหรียญชุดนี้มีคุณสมบัติพิเศษ (canonical coin system) แต่ลองรันกับ coins=[1,3,4], amount=6 ดู

เฉลย

บั๊ก: greedy ไม่ใช่ DP และไม่รับประกันคำตอบที่ดีที่สุดเสมอไป กับ coins=[1,3,4], amount=6: greedy จะหยิบ 4 ก่อน (เหลือ 2) แล้วหยิบ 1 สองครั้ง (เหลือ 0) รวม 3 เหรียญ (4+1+1) แต่คำตอบที่ดีที่สุดจริง ๆ คือ 3+3 = 2 เหรียญ ซึ่งน้อยกว่า!

นี่คือความผิดพลาดคลาสสิกที่ AI สร้างบ่อยมาก เพราะ greedy กับเหรียญสหรัฐ/ไทย “ดูเหมือนถูก” (เหรียญพวกนี้บังเอิญเป็น canonical coin system) แต่กับเหรียญชุดอื่นมันพังแบบเงียบ ๆ — โจทย์นี้ ต้องใช้ DP เพราะไม่มีข้อพิสูจน์ทั่วไปว่า greedy ใช้ได้กับทุกชุดเหรียญ

แก้ไข: ใช้ DP tabulation ตามหัวข้อ Worked Example ด้านบน (dp[a] = min(dp[a-c]+1)) ซึ่งรับประกันคำตอบที่ดีที่สุดเสมอ ไม่ว่าเหรียญจะเป็นชุดไหน

บทเรียน: เมื่อ AI เสนอ greedy สำหรับโจทย์ “หาค่าน้อยที่สุด/มากที่สุด” ให้ถามกลับว่า “พิสูจน์ได้ไหมว่าเลือกโลภแบบนี้ไม่มีวันแพ้ทางเลือกอื่น” ถ้าพิสูจน์ไม่ได้ ให้สงสัยไว้ก่อนว่าโจทย์นี้ต้องการ DP

กรณีที่ 2: Graph — เมื่อ AI ลืม visited

มีคนขอให้ AI เขียนฟังก์ชันเดินสำรวจกราฟ และได้โค้ดนี้กลับมา:

def traverse(graph, start):
    order = []
    queue = [start]
    while queue:
        node = queue.pop(0)
        order.append(node)
        for neighbor in graph[node]:
            queue.append(neighbor)      # <-- ?
    return order

โค้ดนี้รันผ่านกับกราฟต้นไม้ (tree) ที่ไม่มีวงจร แต่…ลองหาบั๊กดู กราฟที่มีวงจร เช่น A — B และ B — A จะเกิดอะไรขึ้น

เฉลย

บั๊ก: ไม่มี visited set เมื่อกราฟมีวงจร (cycle) โหนดจะถูกใส่เข้า queue ซ้ำไม่รู้จบ → infinite loop และ order โตไม่หยุด จนหน่วยความจำเต็ม

นี่คือความผิดพลาดคลาสสิกที่ AI สร้างบ่อยมาก เพราะมันทดสอบกับกราฟเล็ก ๆ ที่ไม่มีวงจรแล้ว “ดูเหมือนถูก”

แก้ไข: เพิ่ม visited เพื่อไม่เยี่ยมโหนดเดิมซ้ำ

from collections import deque

def traverse(graph, start):
    order = []
    visited = {start}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return order

บทเรียน: เมื่อ AI ให้โค้ดกราฟมา ให้ตรวจหา visited เป็นอันดับแรก และทดสอบกับกราฟที่มีวงจรเสมอ

🎮 เกมเดฟ: A* Pathfinding และ DP เก็บทอง

BFS ที่เราเพิ่งเห็นด้านบนคือหัวใจของระบบนำทางศัตรู (enemy pathfinding) ในเกมจริง แต่เกมส่วนใหญ่อยากให้ศัตรูเดินไปหาผู้เล่น “อย่างฉลาด” ไม่ใช่แค่แผ่ค้นหาทุกทิศทางเท่า ๆ กัน — นี่คือจุดที่ A* เข้ามาแทน BFS ด้วยการเติม heuristic เข้าไปช่วยจัดลำดับว่าควรสำรวจ tile ไหนก่อน ในทางกลับกัน ตาราง DP แบบ Unique Paths ที่เราเพิ่งทำ ก็แปลงเป็นปัญหาเกมได้ทันที: แทนที่จะ “นับเส้นทาง” ให้ลองหาเส้นทางที่ เก็บทองได้เยอะที่สุด

A* Pathfinding บน Tile Grid

ให้ tile แต่ละช่องเป็นโหนด และ tile ที่อยู่ติดกัน (บน/ล่าง/ซ้าย/ขวา) เป็น edge เหมือนโจทย์ “เส้นทางสั้นที่สุดในตาราง” ด้านบนทุกประการ แต่ BFS มีข้อเสียเวลากราฟใหญ่: มันแผ่ค้นหาเท่ากันทุกทิศทาง แม้ทิศที่ห่างจากเป้าหมายก็ยังถูกสำรวจเต็มที่ — เสียเวลาโดยใช่เหตุเมื่อแมพเป็นพัน tile

A* แก้ปัญหานี้ด้วยการเปลี่ยน queue ธรรมดาให้เป็น priority queue ที่จัดลำดับด้วย f = g + h โดย g คือระยะที่เดินมาแล้วจริง ๆ และ h คือ heuristic ที่ประมาณระยะที่เหลือ (ในที่นี้ใช้ Manhattan distance: |dx| + |dy| เพราะเดินได้แค่ 4 ทิศ ไม่มีแนวทแยง) ผลคือ A* สำรวจ tile ที่ “ดูมีแนวโน้มจะใกล้เป้าหมาย” ก่อนเสมอ แทนที่จะสำรวจทุกทิศเท่ากันแบบ BFS

import heapq

def manhattan(a: tuple[int, int], b: tuple[int, int]) -> int:
    return abs(a[0] - b[0]) + abs(a[1] - b[1])

def astar(grid: list[list[int]], start: tuple[int, int],
          goal: tuple[int, int]) -> list[tuple[int, int]]:
    rows, cols = len(grid), len(grid[0])
    frontier = [(manhattan(start, goal), 0, start)]   # (f, g, tile)
    came_from = {start: None}
    cost_so_far = {start: 0}
    while frontier:
        _, g, current = heapq.heappop(frontier)
        if current == goal:
            break
        for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            nr, nc = current[0] + dr, current[1] + dc
            neighbor = (nr, nc)
            if not (0 <= nr < rows and 0 <= nc < cols) or grid[nr][nc] == 1:
                continue                       # นอกตาราง หรือกำแพง
            new_cost = g + 1
            if neighbor not in cost_so_far or new_cost < cost_so_far[neighbor]:
                cost_so_far[neighbor] = new_cost
                priority = new_cost + manhattan(neighbor, goal)
                heapq.heappush(frontier, (priority, new_cost, neighbor))
                came_from[neighbor] = current
    path, node = [], goal
    while node is not None:
        path.append(node)
        node = came_from.get(node)
    return path[::-1]

ทั้ง BFS และ A* รับประกันเส้นทางสั้นที่สุดในกราฟไม่มีน้ำหนัก (unweighted) เหมือนกัน — ความต่างคือ A สำรวจ tile น้อยกว่ามาก* เมื่อ heuristic นำทางถูกทิศ ยิ่งแมพใหญ่ ยิ่งเห็นผลชัด (ดูแบบฝึกหัดข้อ 1)

รูป: tile สีเทาเข้มคือกำแพง เส้นทางสีส้มคือเส้นทางที่ A เลือกจาก S ไป G*

ลองคลิก tile ในวิดเจ็ตข้างบนเพื่อวางกำแพงเอง แล้วกด find path ดูว่า A* เลี่ยงกำแพงและวิ่งตรงไปหาเป้าหมายอย่างไร

DP เก็บทองให้ได้มากที่สุด

ใช้กราฟตารางเดียวกับ Unique Paths แต่เปลี่ยนโจทย์: แต่ละช่องมีทองอยู่ grid[i][j] เหรียญ หุ่นยนต์เดินได้แค่ขวา/ลง อยากรู้ว่าเก็บทองได้มากที่สุดกี่เหรียญเมื่อไปถึงมุมขวาล่าง

วิธี “โง่” ที่สุดคือ recursion ลองทุกเส้นทางแล้วเทียบผลรวมมากสุด — ใช้ได้กับตารางเล็ก แต่ระเบิดเป็น exponential เพราะเส้นทางซ้ำกันถูกคำนวณซ้ำเหมือน unique_paths แบบ recursion ตรง ๆ ที่เห็นด้านบน แก้ด้วย DP แบบเดียวกัน แค่เปลี่ยนจาก “บวก 1” (นับเส้นทาง) เป็น “เลือกทางที่ดีที่สุด” (max):

dp[i][j] = grid[i][j] + max(dp[i-1][j], dp[i][j-1])
dp[0][0] = grid[0][0]
dp[0][j] = dp[0][j-1] + grid[0][j]   (แถวบนสุด เดินทางเดียว)
dp[i][0] = dp[i-1][0] + grid[i][0]   (คอลัมน์ซ้ายสุด เดินทางเดียว)

def max_gold(grid: list[list[int]]) -> int:
    rows, cols = len(grid), len(grid[0])
    dp = [[0] * cols for _ in range(rows)]
    dp[0][0] = grid[0][0]
    for j in range(1, cols):
        dp[0][j] = dp[0][j - 1] + grid[0][j]
    for i in range(1, rows):
        dp[i][0] = dp[i - 1][0] + grid[i][0]
    for i in range(1, rows):
        for j in range(1, cols):
            dp[i][j] = grid[i][j] + max(dp[i - 1][j], dp[i][j - 1])
    return dp[rows - 1][cols - 1]

โครงเดียวกับ unique_paths เป๊ะ — เปลี่ยนแค่ + เป็น max และบวกค่าทองของช่องปัจจุบันเข้าไป ความซับซ้อนยังเป็น O(m·n) เหมือนเดิม

ลองใช้วิดเจ็ตข้างบน (ตาราง 4×5 เหมือนโจทย์ Unique Paths) แล้วจินตนาการว่าแต่ละช่องมีค่าทองแทนที่จะเป็น “1” — แต่ละช่องยังคงถูกเติมจากช่องบนกับช่องซ้ายเหมือนเดิม เพียงแค่กติกาการรวมค่าเปลี่ยนจากบวกเป็นเลือกทางที่ดีที่สุด

แบบฝึกหัดเกม

1. BFS vs A บนตาราง* — ทั้ง BFS และ A* หาเส้นทางสั้นที่สุดในตารางไม่มีน้ำหนักได้เหมือนกัน แล้ว A* ดีกว่าตรงไหน ลองอธิบายว่าทำไมบนแมพขนาด 100×100 tile ที่ไม่มีสิ่งกีดขวางเลย A* น่าจะสำรวจ tile น้อยกว่า BFS มากแค่ไหน

เฉลย

BFS แผ่ค้นหาเท่ากันทุกทิศทางจนกว่าจะเจอเป้าหมาย เท่ากับสำรวจ tile ในรัศมีวงกลม (บนกราฟตาราง = ทรงข้าวหลามตัด) รอบจุดเริ่มต้นก่อนเสมอ แม้ทิศที่ห่างจากเป้าหมายไปคนละทางก็ยังถูกสำรวจเต็มที่ ส่วน A* ใช้ f = g + h จัดลำดับ priority queue ให้ tile ที่ heuristic บอกว่า “ใกล้เป้าหมาย” ถูกดึงออกมาสำรวจก่อนเสมอ ทำให้การค้นหาเอนไปทางเป้าหมายเป็นเส้นตรง (คล้ายกรวยแคบ ๆ แทนวงกลมเต็มวง) ยิ่งระยะทางจริงระหว่าง S กับ G ไกล A* ยิ่งประหยัด tile ที่ต้องสำรวจเมื่อเทียบกับ BFS ได้มากขึ้นตามสัดส่วน

2. Heuristic ต้อง admissible — ถ้าเปลี่ยน heuristic ในโค้ด A* ด้านบนจาก manhattan(a, b) เป็น manhattan(a, b) * 2 จะเกิดอะไรขึ้นกับเส้นทางที่ได้

เฉลย

Heuristic ที่ถูกต้อง (admissible) ต้องไม่ประเมินระยะทางเกินจริงเด็ดขาด — Manhattan distance บนกราฟที่เดินได้ 4 ทิศเป็น admissible พอดี เพราะเป็นระยะทางจริงขั้นต่ำที่เป็นไปได้ (ไม่มีทางลัดกว่านี้) แต่ manhattan(a, b) * 2 ประเมินเกินจริง ทำให้ A* รีบเลือก tile ที่ดู “ใกล้เป้าหมาย” มากเกินไปโดยไม่รอเทียบเส้นทางอื่นที่ g ถูกกว่า ผลคือ A* อาจคืนเส้นทางที่ไม่สั้นที่สุด (สูญเสียการรับประกัน optimality) แม้จะยังหาเจอทางไปถึงเป้าหมายได้ก็ตาม — นี่คือเหตุผลที่ต้องเลือก heuristic อย่างระมัดระวัง ไม่ใช่ยิ่งมากยิ่งดี

3. เขียน recurrence สำหรับ min-cost — แทนที่จะเก็บทองมากสุด ถ้าโจทย์เปลี่ยนเป็น “ทางเดินแต่ละช่องมีค่าพลังงานที่ต้องเสีย cost[i][j] ต้องการเส้นทางที่เสียพลังงานน้อยที่สุด” recurrence จะเปลี่ยนยังไง

เฉลย

เปลี่ยนแค่ max เป็น min เท่านั้น โครงสร้างเหมือนเดิมทุกอย่าง:

def min_cost(cost: list[list[int]]) -> int:
    rows, cols = len(cost), len(cost[0])
    dp = [[0] * cols for _ in range(rows)]
    dp[0][0] = cost[0][0]
    for j in range(1, cols):
        dp[0][j] = dp[0][j - 1] + cost[0][j]
    for i in range(1, rows):
        dp[i][0] = dp[i - 1][0] + cost[i][0]
    for i in range(1, rows):
        for j in range(1, cols):
            dp[i][j] = cost[i][j] + min(dp[i - 1][j], dp[i][j - 1])
    return dp[rows - 1][cols - 1]

นี่คือสิ่งที่ทำให้ grid-DP มีประโยชน์มาก: แค่เปลี่ยนตัวรวมค่า (+ → นับเส้นทาง, max → เก็บมากสุด, min → เสียน้อยสุด) โครงลูปเติมตารางยังเหมือนเดิมทุกครั้ง

4. Spot the bug — โค้ด max_gold นี้ลืมอะไรไป (บั๊กจะโผล่เมื่อ grid มีค่าติดลบ เช่น ช่องที่เป็นกับดักเสียแต้ม)

def max_gold(grid):
    rows, cols = len(grid), len(grid[0])
    dp = [[0] * cols for _ in range(rows)]
    for i in range(rows):
        for j in range(cols):
            best = max(dp[i - 1][j] if i > 0 else 0,
                       dp[i][j - 1] if j > 0 else 0)
            dp[i][j] = grid[i][j] + best
    return dp[rows - 1][cols - 1]

เฉลย

จริง ๆ แล้วโค้ดนี้ ถูกต้อง สำหรับกรณีทั่วไป (i > 0 else 0 และ j > 0 else 0 จัดการ base case ให้แล้ว) แม้ grid[0][0] จะติดลบก็ยังคำนวณถูก แต่บั๊กที่แอบแฝงอยู่คือ: recurrence นี้ไม่รองรับกำแพง/ช่องเดินไม่ได้ เหมือนที่ A* จัดการได้ (ผ่าน grid[nr][nc] == 1) ถ้าโจทย์เพิ่มเงื่อนไข “บางช่องเดินผ่านไม่ได้เลย” เข้ามา โค้ดนี้จะยังคำนวณ dp[i][j] จากช่องกำแพงราวกับเดินผ่านได้ปกติ ต้องเพิ่มเช็คว่าถ้าช่องปัจจุบันเป็นกำแพง ให้ตั้ง dp[i][j] = -infinity (หรือข้ามไปเลย) ก่อน — บทเรียน: grid-DP ที่ใช้ได้กับตารางเปิดโล่งอาจพังเงียบ ๆ ทันทีที่โจทย์เพิ่มกำแพง/สิ่งกีดขวางเข้ามา ถ้าไม่เพิ่มเงื่อนไขกันเอง

โจทย์ท้าทาย

1. Terrain ที่มีน้ำหนัก (weighted A)* — ในเกมจริง ทุก tile ไม่ได้ใช้เวลาเดินเท่ากัน: พื้นหญ้าปกติ cost=1, โคลน cost=3, น้ำตื้น cost=5 จงปรับ astar() ด้านบนให้รองรับ cost_grid แทนกำแพงแบบ 0/1 ล้วน ๆ (ใบ้: new_cost = g + cost_grid[nr][nc] แทน g + 1 — แต่ทำไม heuristic Manhattan ยังต้อง “ไม่ประเมินเกินจริง” อยู่)

แนวทาง

เปลี่ยนแค่บรรทัดคำนวณ new_cost จาก g + 1 เป็น g + cost_grid[nr][nc] โครง priority queue และ came_from เหมือนเดิมทุกอย่าง — นี่แหละคือ A* เต็มรูปแบบ (ต่างจาก Dijkstra แค่ที่มี heuristic ช่วยจัดลำดับ) จุดสำคัญ: ถ้า terrain มีต้นทุนต่ำสุดที่เป็นไปได้คือ min_cost (เช่น 1 สำหรับหญ้า) heuristic ต้องคูณด้วย min_cost นั้นด้วย เช่น manhattan(a, b) * min_cost ไม่ใช่ manhattan(a, b) เฉย ๆ — ไม่งั้น heuristic จะประเมินเกินจริงเมื่อ terrain ส่วนใหญ่แพงกว่า 1 เสมอ (เสีย admissibility เหมือนข้อ 2) กรณีทั่วไปสุด ถ้าไม่รู้ต้นทุนต่ำสุดล่วงหน้า ให้ตั้ง heuristic = 0 ตลอด (จะกลายเป็น Dijkstra ล้วน ๆ) ปลอดภัยเสมอแต่ช้ากว่า

2. เลือกไอเทมใส่กระเป๋าให้ค่าพลังสูงสุด (knapsack) — ตัวละครมีกระเป๋าที่รับน้ำหนักได้ไม่เกิน capacity มีไอเทมให้เลือก [(weight, power), ...] แต่ละไอเทมหยิบได้ครั้งเดียว (0/1 knapsack) ต้องการชุดไอเทมที่ให้ค่าพลังรวมมากที่สุดโดยน้ำหนักรวมไม่เกิน capacity นี่ต่างจาก grid-DP ยังไง แล้วสถานะ DP ควรเป็นอะไร

แนวทาง

grid-DP มีมิติสถานะเป็น “ตำแหน่งบนตาราง” (i, j) แต่ knapsack มีมิติสถานะเป็น “ไอเทมที่พิจารณาไปแล้วกี่ชิ้น” × “น้ำหนักที่เหลือ” นิยาม dp[k][w] = ค่าพลังสูงสุดที่ได้จากการเลือกไอเทม k ชิ้นแรก โดยน้ำหนักรวมไม่เกิน w recurrence สำหรับไอเทมชิ้นที่ k (weight wt, power pw):

dp[k][w] = dp[k-1][w]                                    ถ้า wt > w (ใส่ไม่ได้)
dp[k][w] = max(dp[k-1][w], dp[k-1][w-wt] + pw)           ถ้า wt <= w (เลือกใส่หรือไม่ใส่)

เติมตารางจาก k=0 ถึง k=len(items), w=0 ถึง capacity คำตอบอยู่ที่ dp[len(items)][capacity] ความซับซ้อนคือ O(len(items) × capacity) — เหมือน grid-DP ตรงที่เติมตาราง 2 มิติแบบ bottom-up ไล่ทีละแถว แต่ต่างตรงมิติที่สองไม่ใช่ตำแหน่งบนแผนที่ แต่เป็น “งบประมาณน้ำหนักที่เหลือ” (นี่คือรูปแบบ DP คลาสสิกที่เรียกว่า 0/1 Knapsack ใช้ได้กับ “loadout” แทบทุกเกมที่มีข้อจำกัดเรื่องน้ำหนัก/ช่อง/mana)

เจาะลึกเพิ่มเติม

• MIT 6.006 — Introduction to Algorithms (OpenCourseWare) — บทเรียน DP และ graph search ฟรี
• Stanford CS161 — Design and Analysis of Algorithms — ครอบคลุม BFS/DFS และเส้นทางสั้นที่สุด
• CLRS — Introduction to Algorithms บทที่ 14–15 (Dynamic Programming) และบทที่ 20–22 (Elementary Graph Algorithms, BFS/DFS) — ตำรามาตรฐานที่พิสูจน์ correctness ของทุกอัลกอริทึมอย่างเข้มงวด
• Kleinberg & Tardos — Algorithm Design — อธิบายวิธี “คิด” ออกแบบ DP และกราฟตั้งแต่ศูนย์ เก่งเรื่องสอนกระบวนการตั้งสมการเวียนเกิดมากกว่าแค่ท่องสูตร
• Sedgewick & Wayne — Algorithms (4th ed.) — โค้ดตัวอย่างกราฟที่อ่านง่าย ครอบคลุม adjacency list/matrix และ BFS/DFS อย่างละเอียด พร้อมภาพประกอบ
• Erickson — Algorithms (ฟรีออนไลน์) — บทเรื่อง Dynamic Programming ยอดเยี่ยมมาก อธิบายวิธี “คิดหา recurrence” เป็นขั้นตอนที่ทำตามได้จริง ไม่ใช่แค่โชว์คำตอบสำเร็จรูป
• Roughgarden — Algorithms Illuminated — อธิบาย DP และกราฟแบบเข้าใจง่ายแต่ยังรักษาความเข้มงวด เหมาะเป็นคู่มืออ่านคู่กับ Stanford CS161
• Visualgo.net — แอนิเมชันแสดงการทำงานของ BFS/DFS แบบโต้ตอบได้ ช่วยให้เห็นภาพลำดับการสำรวจ