Deriving state from previous state [mp]

Micro pattern¶

Description¶

Compute a new state from completed earlier states instead of rebuilding it from the original input.

Problems¶

Construct the next object¶

Extend a collection or transform the preceding generated object.

• 118. Pascal's Triangle (Top Easy)
• 38. Count and Say (Top Medium)
• 78. Subsets (Top Medium)

Dynamic-programming transition¶

Derive a counting or optimal state from already solved dependencies.

• 53. Maximum Subarray (Top Easy)
• 70. Climbing Stairs (Top Easy)
• 198. House Robber (Top Easy)
• 746. Min Cost Climbing Stairs (Google Prep)
• 62. Unique Paths (Top Medium)
• 322. Coin Change (Top Medium)
• 152. Maximum Product Subarray (Top Hard)
• 91. Decode Ways (Top Hard)
• 309. Best Time to Buy and Sell Stock with Cooldown (Top Hard)
• 10. Regular Expression Matching (Top Hard)
• 139. Word Break (Top Hard)
• 312. Burst Balloons (Top Hard)
• 509. Fibonacci Number (Dynamic Programming)
• 1137. N-th Tribonacci Number (Dynamic Programming)
• 740. Delete and Earn (Dynamic Programming)
• 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)
• 673. Number of Longest Increasing Subsequence (Dynamic Programming)
• 1218. Longest Arithmetic Subsequence of Given Difference (Dynamic Programming)
• 1027. Longest Arithmetic Subsequence (Dynamic Programming)
• 1143. Longest Common Subsequence (Dynamic Programming)
• 1035. Uncrossed Lines (Dynamic Programming)
• 1312. Minimum Insertion Steps to Make a String Palindrome (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)
• 188. Best Time to Buy and Sell Stock IV (Dynamic Programming)
• 96. Unique Binary Search Trees (Dynamic Programming)
• 518. Coin Change II (Dynamic Programming)
• 377. Combination Sum IV (Dynamic Programming)
• 474. Ones and Zeroes (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)
• 790. Domino and Tromino Tiling (Dynamic Programming)

Tree aggregation¶

Complete child summaries before computing a parent summary.

• 124. Binary Tree Maximum Path Sum (Top Hard)
• 337. House Robber III (Dynamic Programming)

DAG aggregation¶

Propagate completed predecessor summaries along outgoing edges.

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