Dynamic programming [mp]

Micro pattern¶

Description¶

Define reusable states and transitions so overlapping subproblems are solved once in dependency order.

Problems¶

Constant-space linear DP¶

Keep only the few preceding scalar states needed by each transition.

• 53. Maximum Subarray (Top Easy)
• 70. Climbing Stairs (Top Easy)
• 198. House Robber (Top Easy)
• 746. Min Cost Climbing Stairs (Google Prep)
• 152. Maximum Product Subarray (Top Hard)
• 91. Decode Ways (Top Hard)
• 309. Best Time to Buy and Sell Stock with Cooldown (Top Hard)
• 509. Fibonacci Number (Dynamic Programming)
• 1137. N-th Tribonacci Number (Dynamic Programming)
• 740. Delete and Earn (Dynamic Programming)
• 714. Best Time to Buy and Sell Stock with Transaction Fee (Dynamic Programming)
• 123. Best Time to Buy and Sell Stock III (Dynamic Programming)
• 790. Domino and Tromino Tiling (Dynamic Programming)

One-dimensional table¶

Store states along one dimension and update them in dependency order.

• 62. Unique Paths (Top Medium)
• 322. Coin Change (Top Medium)
• 139. Word Break (Top Hard)
• 64. Minimum Path Sum (Dynamic Programming)
• 63. Unique Paths II (Dynamic Programming)
• 120. Triangle (Dynamic Programming)
• 931. Minimum Falling Path Sum (Dynamic Programming)
• 221. Maximal Square (Dynamic Programming)
• 516. Longest Palindromic Subsequence (Dynamic Programming)
• 72. Edit Distance (Dynamic Programming)
• 712. Minimum ASCII Delete Sum for Two Strings (Dynamic Programming)
• 115. Distinct Subsequences (Dynamic Programming)
• 1143. Longest Common Subsequence (Dynamic Programming)
• 1035. Uncrossed Lines (Dynamic Programming)
• 1312. Minimum Insertion Steps to Make a String Palindrome (Dynamic Programming)
• 96. Unique Binary Search Trees (Dynamic Programming)
• 518. Coin Change II (Dynamic Programming)
• 377. Combination Sum IV (Dynamic Programming)
• 2140. Solving Questions With Brainpower (Dynamic Programming)
• 2466. Count Ways To Build Good Strings (Dynamic Programming)
• 983. Minimum Cost For Tickets (Dynamic Programming)

Two-dimensional matching table¶

Represent relationships between prefixes of two structured sequences.

• 10. Regular Expression Matching (Top Hard)
• 72. Edit Distance (Dynamic Programming)
• 712. Minimum ASCII Delete Sum for Two Strings (Dynamic Programming)
• 115. Distinct Subsequences (Dynamic Programming)
• 1143. Longest Common Subsequence (Dynamic Programming)
• 1035. Uncrossed Lines (Dynamic Programming)

Precomputed feasibility table¶

Fill a table of valid ranges before using those ranges in search.

• 131. Palindrome Partitioning (Top Hard)

Memoized suffix search¶

Cache recursive suffix results so repeated decompositions reuse them.

• 140. Word Break II (Top Hard)

Interval DP¶

Solve shorter intervals before combining them into longer ones.

• 312. Burst Balloons (Top Hard)
• 516. Longest Palindromic Subsequence (Dynamic Programming)
• 1312. Minimum Insertion Steps to Make a String Palindrome (Dynamic Programming)

Tree DP¶

Combine reusable child summaries at each parent.

• 124. Binary Tree Maximum Path Sum (Top Hard)
• 96. Unique Binary Search Trees (Dynamic Programming)
• 95. Unique Binary Search Trees II (Dynamic Programming)
• 337. House Robber III (Dynamic Programming)

Indexed subsequence states¶

Track the best length or number of ways ending at each position or derived key.

• 673. Number of Longest Increasing Subsequence (Dynamic Programming)
• 1218. Longest Arithmetic Subsequence of Given Difference (Dynamic Programming)
• 1027. Longest Arithmetic Subsequence (Dynamic Programming)

Capacity-constrained states¶

Update amount or resource-capacity states according to item reuse rules.

• 518. Coin Change II (Dynamic Programming)
• 377. Combination Sum IV (Dynamic Programming)
• 474. Ones and Zeroes (Dynamic Programming)

Graph-path states¶

Propagate per-path summaries through a DAG in topological order.

• 1857. Largest Color Value in a Directed Graph (Graph Theory)