интервальное ДП
EN: interval DP
Динамическая программа, состояние которой — непрерывный срез входа: dp[i][j] — лучший ответ для элементов с индекса i по j. Чтобы решить срез, перебирается каждая точка разбиения k (последнее решение внутри среза) и объединяются ответы для двух меньших срезов.