关于动态规划算法有效教学的思考

李建

摘 要：技术科目作为浙江省新高考科目以来，算法加试部分难度不断提高。近几年的考题对计数思想的考查，更标志着程序填空题的难度从代码层面到思维深度的跨越。文章作者将结合思维程度的深入，逐步给出数个经典动态规划问题的思考过程，并提出一种“加一维”的思考方法，切实有效提高学生解决动态规划问题的能力。

关键词：动态规划;状态定义;状态转移;加一维

中图分类号：O221.3 文献标识码：A 收稿日期：2019-04-07 文章编号：1674-120X（2019）24-0117-02

很多教师错误地认为动态规划问题就是背包问题，甚至有教师因为该问题太过抽象，“简单粗暴”地让学生死记背包模型代码，显然这种教学方法是非常不可取的。

下面笔者逐步给出数个经典动态规划问题的解题步骤，建立概念之间的内在联系，让学生了解动态规划算法的本质，并提出“加一维”，切实有效提高学生解决问题的能力。

一、动态规划算法基本原理

在信息学竞赛中，第一次考查动态规划是在IOI1994（国际信息学竞赛）中的“数塔问题”，虽然当时全世界信息學顶尖选手的此题得分率极低，但是现在已经作为DP算法的入门题出现。其模型比较直观，有助于我们理解动态规划算法中的相关概念和性质。很多教师在讲授动态规划时，先罗列相关生涩的概念，很多学生对此无法真正理解。下面我们从一个相对直观的问题出发，一步一步引导学生主动思考，在解决问题的过程中，学生可以逐渐理解问题的本质。

问题一：数塔问题。有一些数字排成数塔的形状，其中第一层有一个数字，第二层有两个数字……第n层有n个数字。现在要从第一层走到第n层，每次只能选择左下方或者右下方的数字，问：“最后将路径上所有数字相加后得到的和最大是多少？”

教师引导思考过程：

（1）从起点到第一行第一列的答案是固定的。

（2）在第一步骤基础上，从起点到第二行的答案也是固定的。

（3）在第三行时，7有两种选择，显然选择累积更大的8才是最优的。若将f[i][j]定义为从第一行第一列到第i行第j列的路径上的数字和的最大值，则到数字7的递推式为：f[3][2] = max（f[2][1] ， f[2][2]）+7。

（4）可得出一般递推式为f[i][j]=max（f[i-1][j-1]，f[i-1][j]）+a[i][j]，我们只需要推到第n行，就可以得到ans=max（f[n][1…n]）。

解法提炼：

（1）状态定义：f[i][j]定义从第一行第一列到第i行第j列的路径上的数字和的最大值。

（2）所求：max（f[n][1…n]）。

（3）状态转移：f[i][j]=max（f[i-1][j-1]，f[i-1][j]）+a[i][j]。

正确性分析：

（1）前面推导的结果不会随着后几行得到的结果而改变——无后效性。

（2）局部最优可以保证全局最优——最优子结构。

这两个性质也是动态规划算法解决问题的先决条件。

二、动态规划的状态定义

问题二：最长上升子序列问题。给定一个长度为n的数字序列，求最长的上升子序列长度。如3，1，2，6，4，5的最长上升子序列为1，2，4，5，故答案为4。

在问题一的基础上，很容易想到如下解法。

（1）状态定义：f[i]定义为到第i个数字为止，能获得最长子序列长度。

（2）所求：f[n]。

（3）状态转移：显然此时很难寻找到f[i]关于f[1…i-1]的递推关系。

无法找到递推关系是由于递推时的大小关系需要第i个数与前面某个确定的数进行比较，而原有的状态定义无法得知哪些数字被选中，故无法直接进行比较，带着这个问题，容易想到新的解法。

（1）状态定义：f[i]定义为到第i个数字为止，且第i个数必须为改子序列的最后一个数字时，所获得的最长子序列的长度。

（2）所求：max（f[1…n]）。

（3）状态转移：f[i] = max（f[j]） + 1|1 <= j <= i - 1，a[j]

该算法的时间复杂度为0（n2），空间复杂度为0（n）。

问题三：最长公共子序列问题。给定两个长度为n的数字序列，求最长的公共子序列长度。如第一个数字序列为1，6，2，5，4，7，第二个数字序列为1，2，5，5，2，7，则最长的公共子序列为1，2，5，7，其长度为4。

顺着问题二的思路，可以得到如下解法。

（1）状态定义：f[i][j]定义为当第一行数字取到第i个，第二行数字取到第j个时，所能得到的最长公共子序列长度，且第i个数字和第j个数字分别为所求子序列的最后一个数字（即这两个数字必须取到）。

（2）所求：max（f[1…n][1…n]）。

（3）状态转移：

该解法状态总数共有n2个，每个状态需要枚举i和j前面所有的p和q，求解单个状态需要的枚举量为（i-1）*（j-1），其时间复杂度是0（n2），总共有n2个状态，故总的时间复杂度为0（n4），空间复杂度为0（n2）。该算法的瓶颈主要在于求解每个状态都需要去枚举前面所有的状态，下面我们尝试使用另外一种状态定义来开拓学生的思路。

（1）状态定义：f[i][j]定义为当第一行数字取到第i个，第二行数字取到第j个时，所能得到的最长子序列长度，且第i个数字和第j个数字不需要为所求子序列的最后一个数字（即这两个数字取到与否都可以）。

（2）所求：f[n][n]。

（3）状态转移：

当a[i]与b[j]相等时，其会对目标值贡献1，而a[i]与b[j]不相等时，显然这两个数字无法配对，故对f[i][j]而言，a[i]和b[j]中必有一个是多余的，故f[i][j]=max（f[i-1][j]，f[i][j-1]）。此时计算f[i][j]的时间复杂度为0（1），故总的时间复杂度为0（n2）。

经过前面三个问题的铺垫，我们对解决动态规划的问题的模式与思考方式有了一定了解，在此基础上，我们再开始对更抽象的背包问题进行解答。

三、动态规划算法在装箱问题中的应用

问题四：装箱问题。有一个箱子容量为V（正整数，0<=V<=20000），同时有n个物品（0

（1）状态定义：f[i][j]定義为放到第i个物品为止，体积为j能否得到，1表示取到，0表示取不到。

（2）所求：V-max（j）|f[n][j]=1。

（3）状态转移：f[i][j]=f[i-1][j-a[i]]|f[i-1][j-a[i]]=1。

优化一：观察状态转移方程，f[i]仅与f[i-1]有关，故我们可以采用滚动数组来优化空间，f[flag][j]=f[！flag][j-a[i]]|f[！flag][j-a[i]]=1，一轮计算完毕后，flag=！flag，此时空间复杂度从0（n*V）优化到0（V）。

优化二：只需要从大到小枚举j就可保证同一个物品不会被计算多次，f[j]=f[j-a[i]]|f[j-a[i]]=1。

拓展思考：如果每个物品有无穷多个呢？

四、“加一维”思想在动态规划问题中的应用

问题五：数塔问题加强版。在问题一的基础上，增加一个条件：有且仅有一次机会可以将路径中的一个数字获得两次，求最后路径中路径上数字的和的最大值。

显然存在几种明显错误的贪心思想：

（1）在问题一基础上，对路径中最大的数字使用额外取一次的机会。

可构造如下反例：

1

1  8

14 8 8

经过问题一的处理，会发现路径为1-8-8，再对路径中最大值8额外取一次，最后结果为25，而显然存在更优的答案为1-1-14，其最后的结果为30。

（2）有了上述反例，又尝试进行如下的贪心策略：将所有数字中最大的数字选定，再以这个数字为起点往上取到顶，往下取到最后一行，又可构造反例如：

1

1   10

11 10 10

按照贪心策略，其路径为1-1-11，结果为24，而存在答案为1-10-10，31。

正确做法就是本文要提出的“加一维”解法，引导思考过程：

（1）在不使用额外机会时，与问题一是完全一样的。

（2）机会使用后，也与问题一是完全一样的。

（3）每个数字都有使用该机会的可能性。

提出解法：

（1）状态定义：f[i][j][k]定义为取到第i行第j列时，机会的状态是k时能获得的目标值最优为多少，k为0表示机会已经使用，k为1表示机会尚未使用。

（2）所求：max（f[n][1..n][0]）。

（3）状态转移：

如果在第i行第j列时，机会依旧存在，则在此之前其机会也必须存在故递推式为：f[i][j][1]=max（f[i-1][j-1][1]，f[i-1][j][1]）+a[i][j]。

如果机会已经被使用，则f[i][j][0]有两种可能性：在此之前机会已经被使用max（f[i-1][j-1][0]，f[i-1][j][0]）+a[i][j]或者对a[i][j]使用取两次的机会max（f[i-1][j-1][1]，f[i-1][j][1]）+2*a[i][j]，我们只需在这两种可能性中取最大值便可。

我们把加入该机会是否被使用的状态作为新的一维，枚举其转移时的所有可能性，巧妙地解决了该问题，且时间复杂度和空间复杂度依旧和原问题同阶。这种技巧也在大量的动态规划问题中适用，当我们无法很轻松地将“不可控的量”交代清楚时，可以将其状态作为单独的一维代入计算。

参考文献：

[1]吴传松.信息学奥赛中“动态规划算法”的教学方法探究[J].中学理科园地，2008（3）：11-13.

[2]廖慧芬，邵小兵.动态规划算法的原理及应用[J].中国科技信息，2005（21）：42.