มีคีย์บอร์ด 4 ปุ่ม: A, Ctrl+A (Select All), Ctrl+C (Copy), Ctrl+V (Paste) เป้าหมาย: กดปุ่มทั้งหมด N ครั้ง ให้ได้ตัว A มากที่สุด ตัวอย่าง Input และ Output Input: N = 7 Output: Maximum Number of As with 7 keystrokes is: 9 วิธีทำ: กด A 3 ครั้ง → Ctrl+A → Ctrl+C → Ctrl+V → Ctrl+V (3 + 1 + 1 + 1 + 1 = 7

Independent Set ใน Binary Tree คือ subset ของโหนดที่ไม่มี edge ใดๆ เชื่อมระหว่างโหนดใน subset นั้น (คือ ไม่มีโหนดใดเป็น parent/child ของอีกโหนดหนึ่งในเซต) เป้าหมาย: หาขนาดของ Largest Independent Set (LIS) ตัวอย่าง Input และ Output Binary Tree: 20 / \ 8 22 / \ \

กำหนดอาร์เรย์จำนวนเต็ม ต้องการหาผลรวมของ subarray ที่ติดกัน (contiguous) ซึ่งมีค่ามากที่สุด Kadanes Algorithm เป็นวิธี Dynamic Programming ที่มีประสิทธิภาพ เก็บค่า ผลรวมสูงสุดที่ลงท้าย tạiตำแหน่งปัจจุบัน ไปเรื่อยๆ ตัวอย่าง Input และ Output Input: {-2, -3, 4, -1, -2, 1, 5, -3} Output: Maximum Sum o

Longest Common Subsequence (LCS) คือ subsequence ที่ปรากฏในทั้งสองสตริง/อาร์เรย์ที่กำหนด เรียงลำดับเดียวกัน (ไม่จำเป็นต้องติดกัน) ปัญหานี้มี Overlapping Subproblems ทำให้ Dynamic Programming เหมาะสม ใช้ตาราง 2 มิติเก็บความยาว LCS ของ prefix ต่างๆ ตัวอย่าง Input และ Output Input: String 1: AGGTAB

ลำดับ Bitonic คือลำดับที่เพิ่มขึ้นก่อน แล้วตามด้วยการลดลง เราต้องการหา subsequence ที่เป็น bitonic และมีความยาวมากที่สุด แนวคิดแก้ปัญหา แบ่งเป็น 2 ส่วน: LIS (Longest Increasing Subsequence): incSubSeq[i] = ความยาว LIS ที่ลงท้ายด้วย array[i] LDS (Longest Decreasing Subsequence): decSubSeq[i] = ความ

มีเมทริกซ์ของตัวอักษรต่างๆ ให้เริ่มจากตัวอักษรหนึ่งตัว แล้วหาเส้นทางที่ยาวที่สุดโดยเดินไปยังตัวอักษรที่มากกว่าตัวปัจจุบันทีละ 1 ตัว (เช่น a → b → c ...) และเคลื่อนที่ได้ 8 ทิศทาง (บน, ล่าง, ซ้าย, ขวา, และ 4 มุม) ตัวอย่าง Input และ Output Matrix: a c d h b a i g f Input: เริ่มจาก e Output: Maximum

Longest Increasing Subsequence (LIS) คือ subsequence ที่สมาชิกแต่ละตัวมีค่ามากกว่าตัวก่อนหน้า เราต้องการหาความยาวของ LIS จากชุดของจำนวนเต็ม ตัวอย่าง Input และ Output Input: {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15} Output: ความยาว LIS = 6 Subsequence: 0, 2, 6, 9, 13, 15 อัลกอริทึม Dyn

ในสตริงที่กำหนด เราต้องการหา substring ที่เป็นพาลินโดรม (อ่านจากหน้าหลังได้เหมือนกัน) และมีความยาวมากที่สุด ปัญหานี้มี subproblems ที่ทับซ้อนกัน (Overlapping Subproblems) ทำให้ Dynamic Programming เหมาะสม เราสามารถใช้ตาราง 2 มิติเก็บผลลัพธ์ของ subproblems ไว้ เพื่อนำไปใช้ต่อโดยไม่ต้องคำนวณซ้ำ ตัวอ

มีเมทริกซ์ที่แต่ละเซลล์มีคะแนน จุดประสงค์คือการหาคะแนนสูงสุดที่สามารถเก็บได้จากกริดนี้โดยใช้การเดินทาง 2 ครั้ง โดยมีเงื่อนไขดังนี้: เงื่อนไขของปัญหา การเดินทางครั้งที่ 1: เริ่มจากมุมซ้ายบน (0,0) และต้องไปถึงมุมซ้ายล่าง การเดินทางครั้งที่ 2: เริ่มจากมุมขวาบน และต้องไปถึงมุมขวาล่าง การเคลื่อนที่: จา

หาผลรวมของตัวเลขแต่ละหลักของทุกตัวเลขในช่วง 1 ถึง n เช่น 54 → 5+4=9 ต้องการผลรวมทั้งหมด ใช้สูตรเรียกซ้ำ: sum(10^d - 1) = sum(10^(d-1) - 1) × 10 + 45 × 10^(d-1) การรับค่าและแสดงผล Input: ขอบเขตบน = 20 Output: Sum of digits in range (1 to 20) is: 102 อัลกอริทึม digitSumInRange(n) Begin if n < 10

หาจำนวนสตริงไบนารีความยาว n ที่ไม่มีเลข 1 ติดกัน ตัวอย่าง n=3: มี 011, 110, 111 ที่มี 1 ติดกัน → เหลือ 5 สตริงที่ไม่มี 1 ติดกัน กำหนด a[i] = จำนวนสตริง i บิตที่จบด้วย 0 และไม่มี 1 ติดกัน b[i] = จำนวนสตริง i บิตที่จบด้วย 1 และไม่มี 1 ติดกัน ความสัมพันธ์แบบเรียกซ้ำ: a[i] = a[i-1] + b[i-1] b[i] = a[i

เกมที่ผู้เล่นทำคะแนนได้ 3, 5, หรือ 10 คะแนนต่อครั้ง กำหนดคะแนนเป้าหมาย n ต้องการหาจำนวนวิธีทำคะแนนรวมเท่ากับ n ได้ ใช้ Dynamic Programming: สร้างตารางเก็บจำนวนวิธีสำหรับคะแนน 0 ถึง n อัปเดตตารางสำหรับแต่ละคะแนนที่เป็นไปได้ (3, 5, 10) การรับค่าและแสดงผล Input: คะแนนเป้าหมาย = 50 Output: Number of w

มี n ส่วน (Section) แต่ละส่วนมี 2 ด้านถนน สร้างอาคารได้ แต่ต้องมีที่ว่างอย่างน้อย 1 ช่องระหว่างอาคาร ต้องการหาจำนวนวิธีก่อสร้างที่เป็นไปได้ แต่ละส่วนมี 4 รูปแบบ: สร้างด้านซ้าย, สร้างด้านขวา, ไม่สร้าง, สร้างทั้งสองด้าน การรับค่าและแสดงผล Input: จำนวนส่วน = 3 Output: Buildings can be constructed in

มีบันได n ขั้น คนเดินจากขั้นที่ 1 ถึงขั้นที่ n กำหนดจำนวนขั้นสูงสุดที่ข้ามได้ใน 1 ก้าว (max) ต้องการหาจำนวนวิธีเดินขึ้นไปถึงขั้นที่ n เช่น max = 2: ways(n) = ways(n-1) + ways(n-2) (เหมือน Fibonacci) การรับค่าและแสดงผล Input: จำนวนขั้น = 10, ขั้นสูงสุดต่อก้าว = 2 Output: Number of ways to reach: 89

ปริศนาคลาสสิก: อาคารมี n ชั้น มีไข่ m ฟอง ต้องการหาจำนวนครั้งทดสอบน้อยที่สุดเพื่อหาชั้นสูงสุดที่ทอยไข่ไม่แตก กติกาสำคัญ: ไข่ไม่แตกที่ชั้น k → ไม่แตกที่ชั้นต่ำกว่า k ทุกชั้น ไข่แตกที่ชั้น k → แตกที่ชั้นสูงกว่า k ทุกชั้น ไข่แตกต้องทิ้ง ไข่ไม่แตกใช้ซ้ำได้ การรับค่าและแสดงผล Input: จำนวนไข่ = 4, ชั้

กำหนดสตริง 2 สตริง: สตริงต้นทาง (Source) และสตริงเป้าหมาย (Target) ต้องการหาจำนวนการแก้ไขขั้นต่ำ (Insert, Delete, Replace) เพื่อแปลงสตริงต้นทางเป็นสตริงเป้าหมาย การรับค่าและแสดงผล Input: สตริง 1: Programming, สตริง 2: Programs Output: The number of changes required to convert Programming to Program

กำหนดจำนวนหลัก n และค่าเป้าหมาย sum ต้องการหาจำนวนตัวเลข n หลักที่ผลรวมของตัวเลขแต่ละหลักเท่ากับ sum (ไม่นับ 0 เป็นหลักแรก) ข้อจำกัด: n = 1 ถึง 100, sum = 1 ถึง 500 การรับค่าและแสดงผล Input: จำนวนหลัก = 3, ผลรวม = 15 Output: Number of values: 69 (มีตัวเลข 3 หลัก 69 ตัวที่ผลรวมตัวเลข = 15) อัลกอริ

มี N สถานีในการเดินทาง เริ่มจากสถานี 0 ถึง N-1 กำหนดตารางค่าใช้จ่ายระหว่างทุกคู่สถานี ต้องการหาต้นทุนขั้นต่ำไปถึงปลายทาง การรับค่าและแสดงผล Input: เมทริกซ์ต้นทุน 0 15 80 90 INF 0 40 50 INF INF 0 70 INF INF INF 0 Output: The minimum cost is 65. เส้นทาง: 0 → 1 (cost 15) → 3 (cost 50) = 65 อัล

กำหนดกราฟมีทิศทางที่มีน้ำหนัก และโหนด u, v ต้องการหาระยะทางสั้นที่สุดจาก u ไป v ที่ใช้เส้นเชื่อมพอดี k เส้น วิธีแก้: เริ่มจาก u ไปยังโหนดติดกันทั้งหมด และเรียกซ้ำ (Recursive) ด้วย k-1 การรับค่าและแสดงผล Input: เมทริกซ์ต้นทุน 0 10 3 2 INF 0 INF 7 INF INF 0 6 INF INF INF 0 u=0, v=3, k=2 Outp

กราฟมีทิศทางเรียกว่าเชื่อมต่ออย่างแข็งแกร่ง (Strongly Connected) เมื่อมีเส้นทางระหว่างทุกคู่ของโหนดในคอมโพเนนต์เดียวกัน วิธีแก้ (Kosarajus Algorithm): ใช้ DFS หาเวลาสิ้นสุด (Finish Time) ของแต่ละโหนด สร้างกราฟทรานสโพส (Transpose Graph) โดยกลับทิศทางเส้นเชื่อมทั้งหมด เรียงโหนดตามเวลาสิ้นสุดมากไปน้อ