Hi everyone! Recently I have been solving some classic interval DP problems, and came across some neat problems. Most of these problems have relatively simple recurrence relations, but the straightforward solutions will not pass in complexity, hence requires an observation to reduce the complexity (generally by reducing the number of states by some pre-computation).
Prerequisites : Introductory interval DP such as Longest Increasing Subsequence, Longest Common Subsequence.
You are given an array of $$$a_1,a_2,\dots,a_n$$$ length $$$n \ (n \leq 500, 1 \leq a_i \leq 1000).$$$ You can perform the following operation any number of times:
- Choose a pair of two neighboring equal elements $$$a_i=a_{i+1}$$$ (if there is at least one such pair).
- Replace them by one element with value $$$a_i + 1$$$. After each such operation, the length of the array will decrease by one (and elements are renumerated accordingly). What is the minimum possible length of the array a you can get?
Solution
