interval DP
RU: интервальное ДП
A dynamic program whose state is a contiguous slice of the input: dp[i][j] is the best answer for the elements from index i through j. To solve a slice, it tries every split point k (the last decision made inside it) and combines the answers for the two smaller slices.