Dynamic Programming (DP) เป็นหนึ่งในพาราดายม์ของอัลกอริทึม แบ่งปัญหาเป็นย่อยปัญหา (Sub-problems) และเก็บผลลัพธ์ของย่อยปัญหาไว้เพื่อนำกลับมาใช้ใหม่ ช่วยลดเวลาคำนวณ
มี 2 ประเภทของเทคนิค DP:
- Overlapping Subproblem (ย่อยปัญหาทับซ้อน)
- Optimal Substructure (โครงสร้างย่อยที่เหมาะสม)
ในส่วนนี้จะครอบคลุมโจทย์ต่อไปนี้:
- Box Stacking Problem
- Collect maximum points in a grid using two traversals
- Compute sum of digits in all numbers from 1 to n
- Count Binary String without Consecutive 1's
- Count number of ways to reach a given score in a game
- Count possible ways to construct buildings
- Count ways to reach the n'th stair
- Edit Distance
- Egg Dropping Puzzle
- Find numbers whose sum of digits equals a value
- Minimum Cost to reach Destination
- Floyd-Warshall Algorithm
- Generate Fibonacci Sequence
- Max number of 'A' with four Keys
- Largest Independent Set Problem
- Largest Sum Contiguous Subarray (Kadane's Algorithm)
- Longest Bitonic Subsequence
- Longest Common Subsequence (LCS)
- Longest consecutive path from a given starting character
- Longest Increasing Subsequence (LIS)
- Longest Palindromic Subsequence Length
- Longest Palindromic Substring
- Matrix Chain Multiplication
- Maximum length of pair-chains
- Max Profit after Buying and Selling Share twice
- Maximum size square submatrix with all 1s
- Maximum Sum Increasing Subsequence
- Maximum sum of a rectangle in Matrix
- Find Minimum cost path from matrix
- Minimum Cost for Polygon Triangulation
- Minimum Tokens to Reach Destination
- Minimum Coin Change Problem
- Minimum Number of Possible Jumps
- Sum of minimum perfect square to reach value
- Mobile Numeric Keypad Problem
- Max Sum by breaking number three times
- Cost of Optimal BST
- Friends Pairing Problem
- Wildcard Pattern Matching Problem
- Palindrome Partitioning Algorithm
- Check possibility of partitioning set of equal sum
- Rod Cutting Problem
- Shortest Common Super-Sequence
- Subset Sum Problem
- Total Non-Decreasing Numbers in N-digit value
- Ugly Numbers
- Vertex Covering Problem
- Weighted Job Scheduling Problem
- Word Wrap Problem
