5
第4-8课：方块消除游戏
source link: https://blog.csdn.net/orbit/article/details/108729354
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
第4-8课：方块消除游戏
前面基础部分我们介绍过简单的串模型的动态规划，在这个系列中，我们又介绍了区间动态规划模型、状态压缩动态规划模型和线性动态规划模型。我们用的算法实现都是尽量使用状态递推关系式直接用递推的方法，大家可能都忘了“备忘录（或状态记忆）”也是动态规划，这一课我们将讲解如何用这种方法来求解方块消除游戏的算法实现。
Jimmy 最近迷上了一款叫做“方块消除”的游戏。游戏的规则是：n 个带颜色的方块排成一列，颜色相同的方块连成一个区域（如果两个相邻的方块颜色相同，则这两个方块属于同一个区域）。游戏时，可以选择一个区域消除，如果消除区域的方块数为 x，则可以得到 $x^2$ 的分数。方块消除后右边的方块自动向左移动。游戏虽然很简单，但是要得高分也不容易，那么问题来了，最高可以得多少分？
这个游戏的有趣之处在于消除方块后自动移动方块，方块移动可能会拼成新的连续区域。消除两个独立的相同颜色方块，可以得 $1^2+1^2=2$ 分，如果这两个独立的同色方块能连成一个连续的区域，则消除这个连续区域可得 $2^2=4$ 分。因此，尽可能的形成连续的区域进行消除，才是得高分的途径。
图（1）消除方块问题示意图
假如给出的颜色方块的序列如图（1）所示，这个序列能得的最高分是 $4^2+3^2+2^2=29$ 分，两个蓝色方块最后消除。
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK