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)

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)

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)

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

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)

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…