Recently I've come up with a problem:
Given $$$n$$$ bowling pins. It costs you $$$c_i$$$ to specially knock down the $$$i^{th}$$$ pin. Only when the $$$i^{th}$$$ pin is specially knocked down, a maximum of $$$l_i$$$ pins to its left and $$$r_i$$$ pins to its right will be normally knocked down. Find the minimum cost to knock down all the pins.
My initial thought is letting $$$\mathrm{F}_{i,\ j}$$$ be the minimum cost to clear all the pins from the $$$i^{th}$$$ to the $$$j^{th}$$$, and optimizing $$$\mathrm F$$$ in a manner similar to Floyd–Warshall, but I've not yet come up with a solid prove or decent solution based on this thought.
We can rephrase the problem as "given $$$n$$$ intervals $$$[a_i, b_i]$$$, you can knock down interval $$$[a_i, b_i]$$$ with cost $$$c_i$$$".
It is a fairly classical dynamic programming problem now. You can start by defining $$$\mathrm{dp}[i]$$$ as the cheapest way to remove all pins up to the $$$i$$$-th. Initially, $$$\mathrm{dp}[i] = \infty$$$. Now, let's start processing the intervals in increasing order of the right coordinate. For an interval $$$[a_i, b_i]$$$ with cost $$$c_i$$$ you can update $$$\mathrm{dp}[b_i] \gets \min(\mathrm{dp}[b_i], c_i + \min(\mathrm{dp}[a_i - 1], \mathrm{dp}[a_i], \mathrm{dp}[a_i + 1], \ldots, \mathrm{dp}[b_i - 1]))$$$. $$$O(n^2)$$$ complexity is easy, $$$O(n \log n)$$$ is also possible.
If the problem is rephrased like this, the order of knocking down intervals doesn't affect the result does it? Because in my initial problem as I understand, the order of knocking pins does affect the result.