| Trick | Difficulty | |
|---|---|---|
| LC 312 Burst Balloons | DP in Intervals (Dynamic) | 6 points |
| LC 1130 Minimum Cost Tree From Leaf Values | DP in Intervals (Dynamic) or Monotonic Queue | 6 points |
| LC 375. Guess Number Higher or Lower II | DP in Intervals (Middle) + MinMax | 6-7 points |
| LC 1000. Minimum Cost to Merge Stones | DP in Intervals (Dynamic, Extra States) | 7 points |
| LC 1039. Minimum Score Triangulation of Polygon | DP in Intervals (Middle) | 5 points |
| LC 664. Strange Printer | DP in Intervals (Middle) | 6 points |
| LC 546. Remove Boxes | DP in Intervals (Middle, Extra States) | 7 points |
| LC 730. Count Different Palindromic Subsequences | DP in Intervals (Boundary, Extra States) | 7 points |
| LC 1312. Minimum Insertion Steps to Make a String Palindrome | DP in Intervals (Boundary) | 5-6 points |
Category: DP in Intervals
DP in Intervals (Break on Boundaries)
Posted on
Summary In this category, given a range alg[i,j], the subproblem is usually reduced to alg[i+1,j], alg[i,j-1], or alg[i+1,j-1] according to the properties of boundaries i and j.
DP in Intervals (Extra States)
Posted on
Summary In this category, given a range alg[i,j], the subproblem is not self contained. To make the subproblem independent to outer ranges, some extra states need to be added.
DP in Intervals (Break in Middle)
Posted on
Summary In this category, given a range alg[i,j], we need to identify a middle point k and change the problem into alg[i,k] and alg[k+1, j]. Details LC 375. Guess Number Higher or Lower II Once we identify this problem as a DP problem, it is not difficult. Given a number from 1 to n, actually…
Hard-to-Detect DP
Posted on
Summary In this post, I will introduce some problems that seem difficult. But once we think of them in another way, they will become DP problems in linear structures or intervals, which are not difficult to solve. OJ Details LC 1049. Last Stone Weight II Think of it in this way: we divide the numbers into…
DP in Intervals (Dynamic)
Posted on
Summary Some problems in this category has something dynamic. Like several elements merge into one element or eliminate one element with the a cost related to its neighbors. The key point of these problems is think backward: think about how the last element is formed. Details Minimum Cost to Merge Stones I There are N…