the listed dp strategy fails if you consider a related problem where we collapse the list of pins every time we hit any so that surviving pins remain adjacent t

the listed dp strategy fails if you consider a related problem where we collapse the list of pins every time we hit any so that surviving pins remain adjacent to each other. in this modified problem, you can get a score of 2 with [-1, 1, -1] by hitting the center pin, then hitting both remaining pins, whereas in the original problem you can only hit the center pin in the optimal sequence. a naive approach would involve looking at the 2**n set of "which pins are remaining", but I think you can do this in quadratic time with dp with the observation that you can only take r_{ij} iff you knock down all the pins in between i and j, and that necessarily precludes taking r_{kl} for i < k < j < l, so you can do a sub-dp to find the optimal value of knocking down those in-between pins. can we do better than quadratic for this related problem? wait, also, I think my solution only requires a linear scan in addition to the recursive call but if we're not careful I think it quickly becomes cubic.