算法代表着用系统的方法描述解决问题的策略机制，北京大学《算法基础》课程将带你一一探索枚举、二分、贪心、递归、深度优先搜索、广度优先搜索、动态规划等经典算法，体会他们巧妙的构思，感受他们利用计算解决问题的独特魅力。顺利完成本课程，你将不但能够掌握这些算法的原理，还能够对这些算法进行灵活应用以及准确实现。本课程的中的编程任务，将充分训练你的思维能力和动手能力，促成全面、缜密思考问题的习惯。达到本门课程的要求，即意味者你具备了初步的算法基础和较强的编程实现能力。
方盒游戏
Loading...
来自 Peking University 的课程
算法基础
283 个评分
从本节课中
动态规划（2）
如何进行动态规划，没有一定之规，需要具体问题具体分析。本模块首先由典型的“最长上升子序列”引入，进一步展示几个较难的动规例题，深入探讨动态规划算法中状态的设计以及状态转移关系的构建。
与讲师见面
Jiaying Liu 刘家瑛, Ph.D.Associate Professor
Institute of Computer Science & Technology
郭 炜讲师
北京大学信息科学技术学院教学所
啊，同学们好，我们还是来讲动态规划，这个没完没了的动态规划。
还好这一次这个题目不是特别难，叫方盒游戏。
游戏耶。
实际上没什么好玩儿的，啊。
它说的是有 N 个方盒，摆成一排。
每个方盒可以有自己的颜色。
连续摆放的同颜色方盒就构成一个大块儿。
下面这个图里面一个个小块都是方盒。
那么连续摆放的若干个方盒，比如4个这是一个大块儿。
那我们这图里面一共就有4个大块儿了。
那你怎么玩儿这个游戏呢？ 很无聊的吧？ 你每次去点击一个方盒，
你点了这个方盒，这个方盒所在的大块儿呢，它就会消失。
你点它，这个就会消失了。
那如果消失的大块儿中共有 k 个方盒，那你就能获得 k 平方个积分儿。
然后这游戏就问你了，给定，开始时的状态。
你作为一个玩家，最多可以获得多少的积分儿？ 这里面有聪明的玩法，是吧？
那我们说，这实际上是一个，这个， 动态规划的这个问题。
你不会写程序，你还玩不了这个游戏。
那么这个输入第一行就是test的case啦，然后每
一组数据有两行，第一行就是有多少个方盒，然后第二行就是每一个方盒的颜色。
它是按从左到右的顺序给出来的。
然后你要对每一组数据求这个最高分儿。
额，这个样例输入输出没什么可看的啊。
那我们看一下基本思路啊。
那一开始一共有 n 个大块儿。
我们考虑的是 一个个的大块儿，而不是独立的这个方盒，对吧？ 我们先算出
从原始的数据推算出有多少个大块儿，然后我们把这些大块儿给它编号。
从左到右编号依次为 0 到 n-1。
那这个第 i 个大块儿的颜色就是 color[i] ，我们要记住，对吧？ 那它包含方块儿的数目当然就是 len[i] 了。
那我们先粗略地想一下。
我假设我想用 click_box(i) 表示从 大块 0 到大块 i 这一段消除以后所能得到的最高分儿。
那整个问题当然就是求 click_box(n-1) 对吧？
但是你会发现，你从 这个思路想下去，你没有办法形成一个递推的关系。
这个 click_box(i) 跟 click_box(i-1)
之间有什么关系呀？ 跟 click_box(i-n) 什么之类的有什么关系啊？ 就想不出来了。
所以我们就要把这个 click_box 这种描述方法给它稍微细化一点。
所谓细化就是复杂化，也就说加个什么条件。
也就是说我们这个用来描述状态的这个 维度要增加一维，那表现在这个 click_box 上面相当于它的参数多了一个。
我们用 click_box(i, j) 表示从编号为 i 的这个大块到编号为
j 的这个大块，这一段 包含 i, j 啊，被消除以后所能得到的最高分儿。
那这时候整个问题呢，就是 click_box(0, n-1)，对吧？
那我们要解决这个问题，我们要解决的问题是 click_box(i, j)。
那我们按照递归啊或者动归的思路我们都在想我们先走一步，然后看看事情会变成什么样。
那我们怎么走这第一步呢？ 你可以考虑，我这第一步是对最右边的那个大块 j 进行处理。
这就叫走一步。
那我们对这个大块儿 j 进行处理，它实际上是有两种处理方式，对吧？ 我们要取其优的。
第一种处理方式，鲁莽，就是直接消除它。
那你直接把它消除以后，消除这个 j
这个大块，你所能得到的分数是 len[j] * len[j]，对吧？
然后，接下来你就要把 j 左边的那些大块儿全部都消完了。
那剩下来的问题就变成，我要消除 j 左边所有的大块儿所能得到的最高分儿是多少，然后把两部分加起来。
那消除 j 左边的大块儿，这个问题实际上就是 click_box( i,
j-1)，唉我们看到这个问题跟原来的原始问题 啊这个形式相同但规模变小了，这是一个好现象。
但这只不过是 第一种处理方式。
就是鲁莽的将其直接消除，它会不会是好的办法呢？不一定，不用高兴的太早。
那我们再看，对这个右边的大块 j，实际上它还有第二种处理方式。
第二种处理方式就是，我不急着把它消掉。
我指望以后它说不定能跟左边的某个同色大块合并。
那样说不定还能得到更多的分数，对吧？ 我们知道，我们合并从越长的这个大块儿，我们一下把它消掉，
得到的分数当然就比这个大块分别几个部分分别消除 分数要高，对吧？
所以我们会期望，期待，j 和它左边的某个同颜色大块儿合并。
但是 j 左边的同颜色的大块儿可能有好多个，我到底跟哪个大块儿合并会比较好呢？
那我只好枚举，对吧？ 左边同颜色大块儿有很多个。
我们要枚举，到底和哪一个大块儿合并。
那我们假设这个 j 和左边的大块儿 k 合并。
那左边的大块 k 是什么？ k 就介于 i 到 j-1
之间，对吧？ 它是小于 i-1 的，小于 j-1 的。
那 j-1 的颜色必然和 j 的颜色不一样，否则就是同一个大块 了，对吧？ 所以这个 k 是大于等于 i，小于 j-1 的。
那这样的 k 可能有多个，我就要枚举这个 k。
对每一个 k 我们都看一下。
我们把大块 j 和大块 k 合并所能得到的最高分是多少，然后我们选一个最优的。
那么，我们把这个 j 和这个大块 k 合并。
所能得到的最高分是什么呢？ 到底是不是我写的这个式子呢？ 这个式子表示什么啊？
这表示，我们先看最后这一部分儿，这部分说的是这个 j 和 k 合并了。
合并了以后呢，我把 j 和 k 一起消掉，这就能得到了一个分儿，对吧？
那么我们要做到把 j 和 k 合并，首先我就要把这个 从 k+1 到 j-1
这一部分给它合并，对吧？ 那从 k+1 到 j-1 这一部分它也有各种 各样的合并方式。
其中最优的合并方式所能得到的分数我们记为click_box(k+1, j-1)。
它跟，原问题形式一致，规模变小了。
然后还有就是这个 k 左边的那些东西也要全部删除，对吧？
k 左边 的那些东西全部删除，所对应的问题就是 click_box(i, k-1) 了对吧？ 这时候所能得到的最高分就是这样。
那我们整个大块 j 跟 k 合并起来所能得到的最高分儿看起来就是这个东西。
这到底对不对呢？ 来想想啊。
啊显然是不对的。
为什么不对啊？因为我给大家讲这个 公式的时候我已经事先说了，这个
k 和 j 合并成一个大块以后，一起把它消掉所能得到的分数是这个东西。
但问题是k 和 j 大块合并以后，我们为什么就要一下子把它消掉呢？
我们为什么不能把它留着，再让它等着跟左边的其他同颜色大块进一步合并呢？
是吧？完全可以这么做嘛。
但是你要这么做的话，用 click_box 怎么描述下面的这个，这样的一个问题呢？ 就描述不了，于是就无法递推下去了。
这时候怎么办呢？ 按照我们的法宝，就是 click_box 对问题的描述还不够细化。
它只有2个参数， 也就是2个维度还不够细化，我们就要加一个什么限制条件，让它变成有3个参数，然后我们-
说不定就可以形成递推关系了。
那我们怎么来进行进一步的细化，就添加新的维度呢？ 我们这么搞一种新的形式，就是 click_box(i,
j, ex_len)。
增加了一个新的维度，对吧？ click_box(i, j, ex_len) 表示什么呢？
表示在大块 j 的右边已经有一个长度为 ex_len 的大块。
那这大块怎么来的我们不管它，可以，可能是在合并的过程中形成的， 对吧？
那这个长度为 ex_len 的大块我们暂且就称为 ex_len。
而且这个 j 的颜色和 ex_len 相同。
注意这点啊。
我们从这种情况下将 i 到 j 以及 ex_len
全部都消除所能得到最高分儿就是用 click_box(i, j, ex_len) 表示。
那时候整个问题变成什么呢？ 整个问题当然就变成了这个 click_box(0,
n-1, 0) 对吧？ 然后， 因为这个 n-1 最后一个大块儿它右边只有长度为
0 的什么 大块了对吧？ 它右边根本就没东西，所以就相当于它右边有一个长度为 0 的大块。
那根据这个式子，我们就能够写出递推关系了。
那我们要求 click_box(i, j,
ex_len) 我们还是 按照这个原先的想法，我们走一步。
走一步处理什么呢？ 我们这一步就是要处理
j 和 ex_len 合并以后的大块，这个大块 Q。
j 和 ex_len 的颜色是一致的，对吧？ 我们肯定要把它合并。
不会把它们分别处理。
我们把它合并以后的大块称为 Q。
现在我们在所做的第一步就是要处理这个Q。
我们对这个Q，实际上也有两种处理方式。
一种方式就是鲁莽的给它消去。
另外一种方式，就是指望这个 Q 将来和 j 左边的什么大块再去合并。
好，那么将 k 直接消除，这种做法所能得到的最高分儿是什么呢？ 首先把这个 Q 消除以后，所能得到的分数就是
len[j] + ex_len的平方，是吧？ 那么，剩下来就是要把
j 左边的那些大块全部都消除，那时候所能得到的最高分儿就是 click_box(i, j-1, 0)。
为什么是 0 啊？因为 j-1 这一块右边都已经消完了，对吧？ 所以
j-1 右边就没有什么大块了，所以它右边的那个大块的长度就是0。
好，这是直接将 Q 消除的这个做法。
那还有一种做法就是我们不着急，Q 我留着，指望它跟
这个 j 左边的某个大块 k 去合并。
那 j 左边可能有好多同颜色的大块，对吧？ 那我们就要枚举这个 k，
看看跟哪一个 k 合并所能得到的分数最高，我们就取最优的。
我们要枚举 可能和 Q 合并的大块。
我们假设大块 k 和 Q 合并。
那 k 是什么？ k 是在 j 的这个左边的啊。
那么 k 的取值范围当然就是从 i 到 j-1。
那么， 假设我们这个 Q 和 k 合并，那这个时候所能得到的最大分数是什么呢？ 我们可以把它写出来，就是这么一个式子。
它为什么是这么一个式子呢？ 是，这式子两部分分别表示什么呢？ 我们先看这个click_box(k+1,
j-1, 0)， 这个是说明什么问题？ 就是你希望让这个 Q 和 k 能够并在一块儿。
那显然，k 和 Q 之间的那些大块儿你必须把它消除掉。
那 k 和 Q 之间的大块儿要消除掉也有各式各样的消法，其中最优的消法它能得到的分数当然就是cli-
ck_box( k+1, j-1, 0)，对吧？ k 和 Q
之间的大块儿他们的编号当然就是，就是从 k+1 到 j-1，对吧？
那这个 j-1 右边它到底有没有和 j-1 同颜色的大块呢？ 它不存在这个问题。
因为 j-1 的右边就是 j，j 是 Q 的一部分。
Q 是要将来留着跟 k 去合并的，所以 Q 是跟
k+1 到 j+1 之间的块如何去消除毫无关系的。
所以说我们把 k+1 到 j-1 这一部分消除，这个事情跟
j-1 右边的东西都没有关系，所以 描述这个问题实际上就是click_box(k+1,
j-1, 0)，因为这个问题跟 j-1 右边的东西毫无关系。
好，这一部分就说的是，把 k 和 Q 之间的这些大块给它 消除。
那 k 和 Q 之间的大块被消除以后， 剩下的部分变成了一个什么样的问题呢？
这时候 k 和 Q 就合在一块了对吧？ 然后，k 和 Q
就合在一块了，但是 i 和 k ，从 i 到 k 之间的大块 依然还没有消除。
那这个时候，剩下的部分问题实际上就变成了click_box(i, k,
len[j]+ ex_len)。
这代表什么意思呢？就是有从 i 到 k 这么多大块都有待消除，而且 k 的右边是一个大块儿。
这个大块儿呢，它的长度为len[j]+ex_len。
为什么长度是 len[j]+ex_len呢？ 这个大块儿不就是 Q 嘛，对吧？这个大块就是 Q。Q 的长度不就是，
就是，j 的长度加上 ex_len，对吧？ 由于这个 Q 的颜色跟
k 是相同的， 它又会被跟 k 合并，所以剩下的问题就是click_box(i,
k, 等于这一块就是 Q，Q 的长度就是len[j]+ex_len是吧？
就是这个 k 的右边会有一个大块，这个大块就是 Q，它的长度是len[j]+
ex_len，然后 Q 的颜色跟 k 一致，将来 k 就会跟 Q 合并。
好啦，那现在我们就写出这个递推式了，对吧？ 就是对这个大块 Q 进行两种方式处理的时候我们都能够写出递推式。
然后我在里面取一个最优的就行了。
当然第二种情况我们就需要枚举这个 k 了。
对吧？ 那现在递推式就写出来了，那接下来我们就要考虑
这个递归的终止条件是什么，对吧？ 比如我要求这个click_box(i, j,
ex_len)的时候 什么时候就能不用递归直接就能得到答案呢？ 递归终止条件是什么，当然这个终止条 件还是比较好分析的。
就是 i=j 呗，你要求click_box(i, j, ex_len)，如果 i=j
那就剩下一个大块儿了，那还不好办吗？ 就不用递归了，是吧？ 就这样。
那， 思路我们就说完了，程序呢就不仔细说了。
因为我们写一个递归 函数它有了这个终止条件又有了递推公式我们就能够写出来了，对吧？ 但是这里面要注意的是，你不能完全用递归的方式去写。
如果用递归 方式会有大量的重复计算，于是就超时了。
所以这道题目我们可以采取 所以的记忆化的递归的办法。
我们用一个score数组，用来存放 这个计算结果。
这个score什么 i, j, k 实际上就相当于这里的click_box(i, j, k)所对应的这个，算出来的这个值。
让我们采取这种记忆化递归的办法就能够 很好的解决这个问题。
那么具体这个程序，同学们自己回去 看一看，我就没有时间仔细去说它了。
这个程序还是 比较简单的啊。
[声音]
