ทุกจำนวนเต็มบวกสามารถเขียนเป็นผลรวมของจำนวนกำลังสอง (Perfect Squares) ได้ ต้องการหา จำนวนพจน์น้อยที่สุด ที่จำเป็น ตัวอย่าง Input และ Output Input: 63 Output: Minimum Squared Term needed: 4 63 = 7² + 3² + 2² + 1² = 49 + 9 + 4 + 1 ทฤษฎีทางคณิตศาสตร์ (Lagranges Four Square Theorem) ทุกจำนวนธรรมชาติ

กำหนด Numeric Keypad แบบมือถือเก่า: 1 2 3 4 5 6 7 8 9 * 0 # กฎ: จากปุ่มปัจจุบัน กดได้เฉพาะ บน, ล่าง, ซ้าย, ขวา (ไม่ได้กดแนวทแยง) และ ห้ามกด * และ # หาจำนวนตัวเลข n หลักที่พิมพ์ได้ตามกฎนี้ ตัวอย่าง Input และ Output Input: n = 3 (3-digit numbers) Output: Possible Combinations: 138 อัลกอริทึม Dynam

กำหนดตัวเลข n ต้องการแยก n เป็น 3 ส่วน: n/2, n/3, n/4 (ปัดทศนิยมทิ้ง) แล้วหาผลรวมสูงสุดที่ได้จากการแยกซ้ำๆ จนไม่คุ้มค่าที่จะแยกต่อ ตัวอย่าง Input และ Output Input: n = 12 Output: Maximum sum after breaking: 13 การคำนวณ: 12 → 6+4+3 = 13 (ดีกว่า 12) 6 → 3+2+1 = 6 (เท่าเดิม หยุด) 4 → 2+1+1 = 4 (เท่าเ

กำหนด Keys ที่เรียงลำดับแล้ว และ Frequency ของแต่ละ Key ต้องการสร้าง Binary Search Tree ที่มี Expected Search Cost น้อยที่สุด Cost = Σ (frequency[i] × depth ของ key[i] ในต้นไม้) ตัวอย่าง Input และ Output Keys = {10, 12, 20} Frequency = {34, 8, 50} Output: Cost of Optimal BST is: 142 ตัวเลือก BST

กำหนดสตริงหลัก (text) และ wildcard pattern ต้องการตรวจสอบว่า pattern ตรงกับ text หรือไม่ Wildcard Symbols: ? - ตรงกับตัวอักษรเดี่ยวใดๆ (exactly 1 character) * - ตรงกับลำดับตัวอักษรใดๆ รวมถึง empty string (0 or more characters) ตัวอย่าง Input และ Output Input: Text: Algorithm Pattern: A*it?m Ou

มีเพื่อน n คน แต่ละคนสามารถ อยู่คนเดียว (Single) หรือ จับคู่ (Pair) กับอีกคนหนึ่งได้ หาจำนวนวิธีทั้งหมดที่เป็นไปได้ หมายเหตุ: คู่ (p, q) และ (q, p) ถือว่าเป็นวิธีเดียวกัน ตัวอย่าง Input และ Output Input: n = 5 Output: Number of ways to pair 5 friends: 26 สูตร Reccurrence กำหนด f(n) = จำนวนวิธีสำห

กำหนดสตริง ต้องการหา จำนวนครั้งน้อยที่สุด (Minimum Cuts) ในการตัดสตริง ทำให้ทุกชิ้นเป็นพาลินโดรม ตัวอย่าง Input และ Output Input: ababbbabbababa Output: Min cuts for Palindrome Partitioning is: 3 Palindromes: a | babbbab | b | ababa อัลกอริทึม Dynamic Programming ฟังก์ชัน minPalPart(str) ใช้ 2 ตา

กำหนดเซตของจำนวนเต็ม ต้องการทราบว่าสามารถแบ่งเป็น 2 subset ที่มี ผลรวมเท่ากัน ได้หรือไม่ ตัวอย่าง Input และ Output Input: {3, 1, 1, 2, 2, 1} Sum = 10 (คู่) Output: True Partitions: {3, 1, 1} และ {2, 2, 1} (ทั้งคู่รวม = 5) อัลกอริทึม Dynamic Programming (Subset Sum) ฟังก์ชัน checkPartition(set, n)

Longest Palindromic Subsequence คือ subsequence ของสตริงที่เป็นพาลินโดรม และมีความยาวมากที่สุด (ต่างจาก Substring ที่ต้องติดกัน) ตัวอย่าง Input และ Output Input: ABCDEEAB Output: The length of the longest palindrome subsequence is: 4 Palindrome: AEEA (หรือ ABBA) อัลกอริทึม Dynamic Programming ฟังก

กำหนด Chain ของเมทริกซ์: A₁, A₂, ..., Aₙ โดยเมทริกซ์ Aᵢ มีขนาด p[i-1] × p[i] การคูณเมทริกซ์มีสมบัติ Associative: (AB)C = A(BC) แต่ จำนวนการคูณสเกลาร์ (scalar multiplications) แตกต่างกันไป ต้องการหาลำดับการคูณที่ใช้ operations น้อยที่สุด ตัวอย่าง Input และ Output Input: arr[] = {1, 2, 3, 4} หมายความ

กำหนด Chain of Pairs: แต่ละคู่ (a, b) โดย a < b เสมอ กฎการต่อยอด: คู่ (x, y) สามารถต่อหลัง (p, q) ได้ก็ต่อเมื่อ q < x เป้าหมาย: หา ความยาวสูงสุด ของ chain ที่สร้างได้ ตัวอย่าง Input และ Output Input: {(5, 24), (15, 25), (27, 40), (50, 60)} Output: Length of maximum size chain is 3 (Chain: (5,

กำหนด Binary Matrix (มีแค่ 0 และ 1) ต้องการหา Square Submatrix ขนาดใหญ่ที่สุด ที่ทุกค่าเป็น 1 ตัวอย่าง Input และ Output Input Matrix (6x5): 0 1 1 0 1 1 1 0 1 0 0 1 1 1 0 1 1 1 1 0 1 1 1 1 1 0 0 0 0 0 Output: Subsquare matrix (ขนาด 3x3): 1 1 1 1 1 1 1 1 1 อัลกอริทึม Dynamic Programming ฟังก์ชัน su

ในการซื้อขายหุ้น ภายในวันเดียวอนุญาตให้ทำธุรกรรมได้สูงสุด 2 ครั้ง (ซื้อ-ขาย ครั้งที่ 1 ต้องเสร็จก่อนครั้งที่ 2 จะเริ่ม) กำหนดราคาหุ้นแต่ละวัน ต้องการหา กำไรสูงสุด ที่เป็นไปได้ ตัวอย่าง Input และ Output Input: {2, 30, 15, 10, 8, 25, 80} Output: Maximum Profit = 100 วิธีทำ: - ครั้งที่ 1: ซื้อที่ 2,

Maximum Sum Increasing Subsequence (MSIS) คือ subsequence ที่: เรียงลำดับเพิ่มขึ้น (Increasing) มีผลรวมของสมาชิกมากที่สุด (Maximum Sum) ตัวอย่าง Input และ Output Input: {3, 2, 6, 4, 5, 1} Output: Maximum Sum Subsequence is: 3 4 5 (Sum = 12, ซึ่งมากกว่า {2, 6} = 8 หรือ {3, 6} = 9) อัลกอริทึม Dyna

กำหนดเมทริกซ์ 2 มิติ ต้องการหา sub-rectangle (สี่เหลี่ยมผืนผ้าย่อย) ที่มีผลรวมของสมาชิกมากที่สุด ตัวอย่าง Input และ Output Matrix (4x5): 1 2 -1 -4 -20 -8 -3 4 2 1 3 8 10 1 3 -4 -1 1 7 -6 Output: (Top, Left) (1, 1) (Bottom, Right) (3, 3) The max sum is: 29 Submatrix: 4

กำหนดเมทริกซ์ค่าใช้จ่าย (cost matrix) และจุดหมายปลายทาง ต้องการหาเส้นทางจาก (0,0) ไปยังจุดหมายที่มีค่าใช้จ่ายรวมน้อยที่สุด กฎการเดิน: จากเซลล์ (i,j) เดินได้เฉพาะ → ขวา (i,j+1), ล่าง (i+1,j), ล่างขวา (i+1,j+1) ตัวอย่าง Input และ Output Cost Matrix (3x3): 1 2 3 4 8 2 1 5 3 Destination: (2, 2)

เมื่อวาดเส้นทแยงมุมที่ไม่ทับซ้อนในรูปหลายเหลี่ยมจนได้สามเหลี่ยม เรียกว่า Triangulation Cost ของ triangulation = ผลรวมของ perimeter (เส้นรอบรูป) ของสามเหลี่ยมทุกอัน ต้องการหา triangulation ที่มี cost น้อยที่สุด ตัวอย่าง Input และ Output Input: จุดของรูปหลายเหลี่ยม 5 จุด {(0,0), (1,0), (2,1), (1,2),

เริ่มจากมุมซ้ายบน (0,0) ของกริด ต้องไปถึงมุมขวาล่าง แต่ละเซลล์มีค่าตัวเลข (บวกหรือลบ) เมื่อเข้าถึงเซลล์ (i,j) โทเคนจะเพิ่ม/ลดตามค่านั้น ต้องการหา โทเคนเริ่มต้นน้อยที่สุด ที่ทำให้เดินทางสำเร็จ กฎการเดินทาง เดินได้เฉพาะ ขวา หรือ ล่าง เท่านั้น ไม่สามารถเข้าสูงเซลล์ (i,j) ได้ถ้าโทเคนปัจจุบัน < ค่าของเ

Floyd-Warshall Algorithm ใช้หา All-Pairs Shortest Path ในกราฟที่มีน้ำหนัก (weighted graph) ผลลัพธ์คือเมทริกซ์ที่แสดงระยะทางสั้นที่สุดระหว่างทุกคู่ของโหนด ตัวอย่าง Input และ Output Input: Cost Matrix (7 โหนด, INF = ไม่มีขอบ) 0 3 6 INF INF INF INF 3 0 2 1 INF INF INF 6 2 0 1 4 2 INF INF

ลำดับฟีโบนัชชี: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... สูตร: F(n) = F(n-1) + F(n-2) โดย F(0)=0, F(1)=1 วิธี Reursive แบบธรรมดาจะมีการคำนวณซ้ำมาก (Exponential Time) ใช้ Dynamic Programming (Bottom-up) เก็บค่าในตาราง → O(n) ตัวอย่าง Input และ Output Input: n = 10 Output: 10th Fibonacci Terms: 55