区间dp从零开始

什么是区间DP？简单来说，就是一个问题，它能被拆分成一个个更小的、连续的子区间问题，并且最终大区间的最优解可以由小区间的最优解推导出来。它的典型特征就是，我们求解dp[i][j]（表示区间[i, j]上的最优解）时，需要依赖所有比[i, j]更短的子区间的最-优解，比如dp[i][k]和dp[k+1][j]。 听着还是有点抽象？没关系，我们直接上题，用题目来撕开它的神秘面纱。 经典例题：石子合并 在一条直线上有N堆石子，每堆石子的重量已知。现在需要将所有石子合并成一堆，每次只能合并相邻的两堆石...