区间动态规划
区间DP：
- 状态：区间左右端点 dp[i][j]
- 阶段：区间长度
- 转移：由外到内
石子合并：前缀和+动态规划
问题特征：问总代价最少，求最优解 -> 动态规划的特征。
条件特征：石子合并，线性数组不断缩小的过程 -> 区间动态规划的特征。
按照区间DP定义状态：
- dp[i][j]：i-j 区间总代价最少
那 dp[i][j] 从哪里来？
从最后一步开始想，考虑合并最后的俩堆石子，一定有一个分界线X。
最后俩堆石子合并 = [第1堆-第X堆] + [第X+1堆-第N堆] + 石子总数
- dp[i][j] = min(dp[1][n], dp[1][x] + dp[x+1][n] + 石子总数)
但分界线X在哪里，我们确定不了，贪心算不出，只能枚举一轮找到最小值。
第1堆到第x堆怎么球呢？
- 寻找分界线m
- 1-x俩堆石子合并 = [第1堆-第m堆] + [第m+1堆-第x堆] + 1-m的石子总数
依此类推, 直到一堆石子。
for(int i=1; i<=n; i++)s[i] = s[i-1] + a[i]; // 前缀和，方便计算[i,j]区间的石子总数int re( int i, int j )if ( i == j ) return 0; // 只剩下一堆int ans = INT_MAX;for( int x = i; x < j; x++ ) // 枚举分界线ans = min( ans, re(i, x) + re(x+1, j) );return ans + s[j] - s[i-1]; // 加上石子总数
最长合法子序列
环形石子合并
石子合并 II
城镇国王
超级括号序列
炸弹人
