How to identify a DP problem:

1. optimal solution of a problem is constructed based on optimal solution of subproblems (same property as greedy)
2. subproblems overlap: subproblems used to construct one problem may also be used to construct another problem

recursion + memo: Compared with DP, recursion is sometimes straightforward. With DP, you may get opportunity to reduce memory usage

• 688. Knight Probability in Chessboard
• 494. Target Sum
• 416. Partition Equal Subset Sum
• 329. Longest Increasing Path in a Matrix
• 1866. Number of Ways to Rearrange Sticks With K Sticks Visible
• 568. Maximum Vacation Days
• 1359. Count All Valid Pickup and Delivery Options

problem

• min/max value
• valid/invalid

• valid solutions

core:

• initial state

• state transition

• 70. Climbing Stairs

• 91. Decode Ways

• 338. Counting Bits (191. Number of 1 Bits)

• 357. Count Numbers with Unique Digits

• 322. Coin Change

• 131. Palindrome Partitioning (backtracking)

• 279. Perfect Squares

• 368. Largest Divisible Subset

• 204. Count Primes

• 264. Ugly Number II (263. Ugly Number，23. Merge k Sorted Lists)

• 313. Super Ugly Number (heap sort)

• 343. Integer Break

• 413. Arithmetic Slices

• 1048. Longest String Chain

• 1787. Make the XOR of All Segments Equal to Zero

• 1216. Valid Palindrome III

word break

• 139. Word Break
• 140. Word Break II (dfs)
• 472. Concatenated Words

enumeration

• 198. House Robber
• 213. House Robber II
• 337. House Robber III
• 376. Wiggle Subsequence
• 276. Paint Fence
• 256. Paint House
• 265. Paint House II (use input memory)

recursion

• 96. Unique Binary Search Trees (catalan number (follow-ups))
• 95. Unique Binary Search Trees II
• 241. Different Ways to Add Parentheses (not DP, recursion)
• 120. Triangle (recursion + memo or dp)

range sum

• 303. Range Sum Query Immutable

• 304. Range Sum Query 2D Immutable

• 363. Max Sum of Rectangle No Larger Than K

• 209. Minimum Size Subarray Sum (two pointers / binary search)

• 523. Continuous Subarray Sum (prefix-sum + variant of 2-sum)

• 560. Subarray Sum Equals K (prefix-sum + variant of 2-sum)

• 1314. Matrix Block Sum

max subarray

• 53. Maximum Subarray (Kadane algorithm)
• 152. Maximum Product Subarray
• 1352. Product of the Last K Numbers

stock

• 121. Best Time to Buy and Sell Stock (53. Maximum Subarray)
• 122. Best Time to Buy and Sell Stock II (greedy)
• 123. Best Time to Buy and Sell Stock III (121. Best Time to Buy and Sell Stock / enumerate state)
• 188. Best Time to Buy and Sell Stock IV (Kadane algorithm / enumerate state)
• 309. Best Time to Buy and Sell Stock with Cooldown (enumerate state with using state machine)
• 714. Best Time to Buy and Sell Stock with Transaction Fee (enumerate state)

longest increasing sequence

• 300. Longest Increasing Subsequence (dp / binary search)
• 334. Increasing Triplet Subsequence
• 354. Russian Doll Envelopes
• Interval Scheduling
  • 646. Maximum Length of Pair Chain
• 1626. Best Team With No Conflicts

Misc

• 32. Longest Valid Parentheses (stack invalid index / dp extends gap)
• 361. Bomb Enemy
• 1931. Painting a Grid With Three Different Colors (bit mask + dfs + dp)

2D

string match

• 10. Regular Expression Matching
• 44. Wildcard Matching (rolling array, add two pointers later)
• 72. Edit Distance (rolling array)
• 161. One Edit Distance (two pointers)
• 115. Distinct Subsequences (rolling array)
• 97. Interleaving String (rolling array)
• 5. Longest Palindromic Substring
• 712. Minimum ASCII Delete Sum for Two Strings
• 718. Maximum Length of Repeated Subarray
• 1143. Longest Common Subsequence
• 2060. Check if an Original String Exists Given Two Encoded Strings

matrix

• 62. Unique Paths (rolling array, combination number) (path)
• 63. Unique Paths II (path, rolling array)
• 64. Minimum Path Sum (path, rolling array)
• 174. Dungeon Game (path, rolling array)
• 221. Maximal Square (height)
• 84. Largest Rectangle in Histogram (not dp, monotonically increasing stack)
• 85. Maximal Rectangle (height, 84. Largest Rectangle in Histogram)
• 750. Number Of Corner Rectangles

1d to 2d

• 132. Palindrome Partitioning II
• 312. Burst Balloons
• 375. Guess Number Higher or Lower II (minmax)

3D

string

• 87. Scramble String (recursion)

Minimax

• 877. Stone Game
• 1140. Stone Game II
• 1686. Stone Game VI (greedy)
• 1690. Stone Game VII

Knapsack Problem

• 0-1 Knapsack Problem
  • 1235. Maximum Profit in Job Scheduling
• Bounded Knapsack Problem
• Unbounded Knapsack problem
  • 518. Coin Change 2
  • 377. Combination Sum IV

Jump Game (dp or greedy kinda of like BFS)

• 45. Jump Game II
• 1326. Minimum Number of Taps to Open to Water a Garden
• 1024. Video Stitching
• 1871. Jump Game VII

左右双向dp

• 1937. Maximum Number of Points with Cost
• 42. Trapping Rain Water