不适合用滚动数组

一开始还是按照搜索的思路去想,

一段连续的值就是一个区间

当题目要求类似于合并一个区间的值, 便可以用区间型动归.

不能用滚动数组优化

• 区间型与坐标型和序列型的区别
  • 其实像坐标型和序列型都是从头到尾的计算, 所以只需要一维去记录这个移动的头的位置在哪里
  • 而区间型可以一头一尾去计算. 所以需要多一个维度去记录这个尾的位置在哪里

题目

1. Stone Game
2. Stone Game II
3. Coins in a line III
4. Burst Balloon
5. Scramble string