แผนการเรียน
/

Practice Session: Dynamic Programming
ตะลุยโจทย์บน CSES และ AtCoder

Day 05: ฝึกฝนทักษะการแก้โจทย์มาตรฐานด้วยหลักการ Smart Recursion

แหล่งฝึกฝนหลัก

CSES Problem Set

https://cses.fi/problemset/list/

AtCoder Educational DP

https://atcoder.jp/contests/dp

ทำไมต้องฝึกบนสองแพลตฟอร์มนี้?

• **CSES (Dynamic Programming Section)**: เน้นโจทย์พื้นฐานที่ "ต้องทำได้" (Foundational Problems) ครอบคลุมรูปแบบมาตรฐาน เช่น การทอนเหรียญ และการเดินในตาราง

• **AtCoder Educational DP Contest**: เป็นชุดโจทย์ A ถึง Z ที่ออกแบบมาเพื่อสอนเทคนิค DP โดยเฉพาะ ตั้งแต่ระดับง่ายไปจนถึงขั้นสูง (เช่น DP on Trees, Digit DP, Bitmask)

• **Clean Problems**: ทั้งคู่มีโจทย์ที่กระชับ วัดความเข้าใจในตัวอัลกอริทึมจริงโดยไม่มีการหลอกลวงที่ซับซ้อนเกินจำเป็น

CSES: Dice Combinations

โจทย์: https://cses.fi/problemset/task/1633

ทอยลูกเต๋า 1-6 ให้ได้ผลรวมเป็น \( n \). จะมีทั้งหมดกี่วิธี? (ตอบแบบ Modulo \( 10^9+7 \))

แนวทางการคิด:

นิยาม \( solve(x) \) คือจำนวนวิธีที่ทำให้ผลรวมเป็น \( x \).
ความสัมพันธ์: \( solve(x) = solve(x-1) + solve(x-2) + ... + solve(x-6) \)
โดยมี Base case คือ \( solve(0) = 1 \)

**เทคนิค**: ใช้ Iterative DP วนลูปจาก \( 1 \) ถึง \( n \) และสะสมผลรวมจาก 6 สถานะก่อนหน้า

CSES: Coin Combinations I

โจทย์: https://cses.fi/problemset/task/1635

มีชุดเหรียญ \( \{c_1, c_2, ..., c_k\} \) ต้องการทอนเงินให้ได้ผลรวม \( x \) มีกี่วิธี? (ลำดับเหรียญต่างกันถือเป็นคนละวิธี)

Recurrence:

\( solve(x) = \sum_{c \in coins} solve(x-c) \)

ข้อควรระวัง:

ต้องทำ Modulo ในทุกขั้นตอนการบวก ปัญหานี้เป็นแนวการนับแบบ Permutations

CSES: Grid Paths

โจทย์: https://cses.fi/problemset/task/1638

หาจำนวนเส้นทางจากมุมซ้ายบนไปยังมุมขวาล่างของตาราง \( n \times n \) โดยเดินได้เฉพาะ "ขวา" หรือ "ลง" และต้องหลบสิ่งกีดขวาง (*)

นิยามสถานะ: \( dp[r][c] \) คือจำนวนวิธีที่มาถึงแถว \( r \) คอลัมน์ \( c \)

if (grid[r][c] == '*') dp[r][c] = 0;
else dp[r][c] = dp[r-1][c] + dp[r][c-1];

Base case: \( dp = 1 \) (ถ้าไม่มีสิ่งกีดขวางที่จุดเริ่ม)

AtCoder: Frog 1

โจทย์: https://atcoder.jp/contests/dp/tasks/dp_a

กบต้องการกระโดดจากหินก้อนที่ 1 ไป \( n \) โดยเลือกกระโดดข้าม 1 หรือ 2 ก้อนได้ เสียพลังงานเท่ากับ \( |h_i - h_j| \). หาค่าพลังงานต่ำสุด

"จุดเริ่มต้นของการคิดแบบ Minimum Cost DP"

\( dp[i] = \min(dp[i-1] + |h_i - h_{i-1}|, dp[i-2] + |h_i - h_{i-2}|) \)

อย่าลืม Base case: \( dp[1] = 0, dp[2] = |h_2 - h_1| \)

AtCoder: Vacation

โจทย์: https://atcoder.jp/contests/dp/tasks/dp_c

ในแต่ละวันเลือกทำกิจกรรม A, B หรือ C เพื่อเก็บคะแนน แต่ละกิจกรรมห้ามทำติดต่อกัน 2 วัน. หาคะแนนรวมสูงสุดใน \( n \) วัน

นิยามสถานะ 2 มิติ: \( dp[i][j] \) คือคะแนนสูงสุดในวันที่ \( i \) เมื่อทำกิจกรรม \( j \)

\( dp[i][A] = a[i] + \max(dp[i-1][B], dp[i-1][C]) \)
\( dp[i][B] = b[i] + \max(dp[i-1][A], dp[i-1][C]) \)
\( dp[i][C] = c[i] + \max(dp[i-1][A], dp[i-1][B]) \)

AtCoder: Knapsack 1

โจทย์: https://atcoder.jp/contests/dp/tasks/dp_d

เลือกสิ่งของที่มีน้ำหนัก \( w_i \) และมูลค่า \( v_i \) ใส่ย่ามที่มีความจุ \( W \) ให้ได้มูลค่าสูงสุด (\( N \le 100, W \le 10^5 \))

ความสัมพันธ์:

\( dp[i][j] = \max(dp[i-1][j], dp[i-1][j - w_i] + v_i) \)

**คำแนะนำเพิ่ม**: สำหรับข้อนี้ความจุ \( W \) มีค่าค่อนข้างใหญ่ การใช้อาเรย์ 1 มิติ (Space Optimization) จะช่วยให้ประหยัดหน่วยความจำได้มาก โดยการวนลูปน้ำหนักย้อนกลับ (Right to Left)

กลยุทธ์การฝึกฝน (Up-solving)

1

ลองคิดด้วยตัวเองอย่างน้อย 20-30 นาที หากติดขัดให้ลองวาด Recursion Tree บนกระดาษเพื่อหาปัญหาย่อยที่ทับซ้อนกัน

2

หากยังทำไม่ได้ ให้อ่าน **Editorial** (คำอธิบายเฉลย) เพื่อทำความเข้าใจลอจิก แต่ **ห้าม** คัดลอก Code ทันที

3

เขียนโปรแกรมใหม่ทั้งหมดด้วยตัวเองจากความเข้าใจที่ได้อ่านมา (นี่คือหัวใจของการพัฒนาทักษะ Implementation)

แหล่งเรียนรู้เพิ่มเติม

CSES Handbook

อ่านบทที่ 7 (Dynamic Programming) เพื่อทบทวนทฤษฎีและดูตัวอย่าง Code มาตรฐาน
https://cses.fi/book/book.pdf

YouTube: Errichto

ค้นหา "DP lecture Errichto" เพื่อดูวิธีการวิเคราะห์โจทย์และการเปลี่ยนจาก Recursion เป็น Iterative อย่างละเอียด

"Smart recursion is practice, not magic."