Interval-Dp

Interval DP (choose the last step / merge equal ends), partition DP into k segments, palindrome tables plus partitioning, and memoizing the whole state when it is too tangled to split

LeetCode 1246 note: interval DP taking the minimum of removing arr[i] alone, removing equal ends together with the inside, or splitting into two parts

LeetCode 1335 note: partition DP into d segments; dp(i, k) = the least difficulty starting at job i with k days left, enumerating where today ends while updating today’s maximum

LeetCode 1745 note: build is_pal[i][j] with interval DP, then try both cut points; three palindromic parts means true, O(n^2)

LeetCode 312 note: choose the last balloon k burst in the range (i, j); at that moment its neighbors are i and j, and the two sides are independent subproblems