张立臣 王小明

摘  要：问题解决能力是目前学生亟待提升的能力之一。围绕动态规划算法教学，介绍了一种以问题解决能力目标为导向的教学设计，通过调整教学内容和教学过程，突出学生问题解决能力的培养和训练，为能力目标导向的课程改革提供了一种新思路。

关键词：问题解决能力;动态规划;算法设计;教学设计

中图分类号：G642       文献标志码：A         文章编号：2096-000X（2021）11-0105-05

Abstract： Currently， it is urgent to promote students' problem solving ability. Focusing on the teaching mode on dynamic programming algorithm， a novel teaching design scheme is introduced oriented by the goal of problem solving ability. The proposed scheme tries to adjust the teaching contents and design process， in which the training and promotion process of the students' problem solving ability is emphasized， then providing a novel idea to the ability-oriented curriculum reform.

Keywords： problem-solving ability; Dynamic Programming; algorithm design; teaching design

目前，以学生为中心的教育改革，比如，OBE（Outcomes-Based Education， 成果导向教育）[1]、系统能力培养教育[2]、计算思维能力培养教育[3]、新工科背景下的教育改革等[4]，越来越突出学生的能力培养。根据学生现有能力水平和毕业应具备的能力要求，教育改革要求教师反向设计教学内容、教学模式、教学案例和教学评价方式。

算法设计与分析是计算机学科的一门专业核心课，主要培养学生计算思维能力以及实际计算问题解决能力[5]。这些能力对学生未来从事计算机相关的教学、科研和工程实践活动具有重要作用。因此，算法课程的教学研究和改革得到了广泛关注，已出版了众多案例丰富的算法教材，开发了大量在线算法课程。本文主要以算法课程中的“动态规划算法”教学为例，设计一种新的能力目标导向的教学设计案例，突出培养和训练学生的问题解决能力，从而为能力目标导向的课程改革提供教学案例参考和教学设计思路。

一、动态规划算法教学

动态规划算法解决的问题是最优化问题，其基本思想是将待求解问题分解成若干子问题，通过对子问题的迭代求解，获得待求解问题的最优解[5]。与分治法不同，动态规划算法更适合那些经分解得到的子问题不互相独立的情形。在动态规划算法中，通过保存已解决子问题的解，可避免大量重复计算，进而提高算法效率。

动态规划算法要求待求解问题具有2个重要性质，即最优子结构性质和子问题重叠性质。最优子结构性质是指，问题的最优解可通过其所包含的子问题的最优解计算得到;子问题重叠性质是指，分解后的问题包含很多重复的子问题。通过记录不同的子问题的解，可以大大减少求解子问题的次数。动态规划算法具有很多实际的应用，因此成为算法课程中的一个难点和重点。

二、动态规划算法教学设计

通过动态规划算法教学，我们将突出训练和培养学生基于计算机解决问题的能力，主要包括：问题分析与建模能力、递推方程的构建能力、基于递推方程寻找最优解的能力、递推方程的算法设计与编程实现能力、递推方程的算法优化与复雜度分析能力、递推方程的算法实验分析能力。

（一）问题分析与建模

对实际问题进行分析并建立形式化模型是基于计算机求解问题的首要任务，对学生的未来职业发展具有重要作用。发现问题比解决问题更为重要。正确建立问题的形式化模型往往意味着完成了问题求解的一半工作。问题分析与建模的关键在于如何选择数学符号并运用适当的公式描述问题，即定义问题的目标和约束条件。我们以如下两个最优化问题作为动态规划算法的教学案例。

问题1（数组不相邻元素的最大和问题） 在具有n个元素的数组中取出一个或多个不相邻的元素，使其和最大。

问题2（0-1背包问题） 给定1个背包和一组物品，已知背包的容量以及每个物品的重量和价值，如何选择装入背包的物品，在不超过背包容量的前提下，使得所装入背包的物品的总价值最大。

一般采用3个步骤对给定的问题进行数学建模。步骤1. 确定问题中已知量和未知量的数学符号;步骤2. 确定问题的优化目标;步骤3. 确定问题的各个约束条件。

对于问题1，用符号a表示给定数组，n表示数组所含元素个数，a[i]则表示数组中第i个元素，i在1和n之间。用大小为n的数组x表示选择了哪些元素，x[i]=1表示选择了元素a[i]。然后，问题1的优化目标可表示为所选择的元素的和最大，可用max？撞ia[i]·x[i]表示。该问题存在两个约束，一是所选择的元素互不相邻，可用x[i]+x[i+1]？燮1表示， 其中，i∈{1，...，n-1}，另一个是x[i]的取值只能为0或1，以表示对应第i个元素是否被选取，即x[i]∈{0，1}，i∈{1，...，n}。综上，问题1的形式化模型可表示为：

同理，问题2的形式化模型可表示为：

其中，w[i]和v[i]分别表示物品i的重量和价值，B表示背包的容量，x[i]表示是否将物品i放入背包，即x[i]=1表示选择了物品i，其中，i∈{1，...，n}。显然，该问题的目标是使得所选择的物品的价值之和最大，约束1保证了装入背包的物品的重量之和不超过背包的容量。

在此基础上，继续选择一些代表性的问题作为课堂和课后练习，以训练和培养学生的问题分析及形式化模型构建能力。常见的动态规划问题包括：

问题3（矩阵连乘问题）有n个矩阵进行乘法运算，如何通过给矩阵连乘时加括号，使得总的乘法次数最少。

问题4（加权区间值调度问题） 给定n个时间区间，每个时间区间包括一个开始时间和一个结束时间，还包括一个权重，如何选择一些时间不重叠的时间区间，使得所选择的时间区间的权重之和最大。

问题5（最大连续子序列和问题） 给定一个含n个元素的序列，请确定一个连续的子序列，使得这个子序列的和最大。

（二）递推方程的算法设计与编程实现

考虑到递推方程的构建是动态规划算法教学的重点和难点，我们将该内容放到最后重点讲解。在此，我们将先给出一个递推方程，然后，基于该递推方程讲解对应问题的算法设计与编程实现，从而培养和提高学生能够基于所构建的递推方程设计相应的算法并能够编程实现的能力。事实上，通过之前学习程序设计语言课程，学生已接触过基于递推方程的算法设计和编程训练。我们将通过两个简单示例对学生进行启发式教学。

递推方程1（数的阶乘）整数n的阶乘的递推方程为：

其中，F（i）表示整数i的阶乘，i∈{1，...，n}，因此，整数n的阶乘为F（n）。

递推方程2（最大值）n个元素中的最大值的递推方程为：

其中，M（i）表示n个元素中的前i个元素的最大值，i∈{1，...，n}，因此，n个元素中的最大值为M（n）。

递推方程3（斐波那契数列）递推方程为：

其中，F（i）表示斐波那契数列的第i个元素的值，i∈{1，...，n}。

选择以上简单示例的原因是学生已在程序设计语言课程学习中掌握了求解这些问题的算法设计方案，从而通过总结这些方案，可以得出通用的基于递推方程设计相应算法的方法和步骤。显然，递推方程一般存在两个方案，一个采用递归策略，另一个采用迭代策略。通过分别给出并分析递推方程的两种算法设计方案，可以使学生加深这两种策略的理解。递推方程1、2和3的递归和迭代算法分别用表1、表2和表3描述。

（三）递推方程的算法优化与复杂度分析

算法时间复杂度分析与算法优化能力是需要学生掌握的重要能力。我们将分别对上述递推方程的两种算法进行时间复杂度分析，得出：这三个算法的迭代算法的时间复杂度均为O（n），前两个问题的递归算法的时间复杂度也为O（n），而第3个问题的递归算法的时间复杂度为O（2n），其中n是元素个数。

需要指出的是，（1）基于递推方程设计递归算法较

为直接和简单，但由于递归算法的调用需要消耗大量的系统资源而导致其效率较迭代算法低很多。特别地，对于斐波那契数列问题，虽然不同的子问题的个数只有n个，但递归算法却需要计算很多重复的子问题（2n个）。比如，在計算F（n）时需要计算F（n-1）和F（n-2），而在计算F（n-1）的过程中，又需要再次计算F（n-2），导致算法时间复杂度极高。通过公式推导，可得出其算法时间复杂度为指数级的。（2） 递归算法是一种很自然的算法，对于包含很多重复子问题的计算问题，可引导学生通过“备忘录方法”解决，即将计算的子问题的结果暂时保存在某个数据结构（一般是数组）中。每当需要计算时，首先检索该子问题是否已保存，若是，则直接返回结果，否则，将进行计算并保存结果。经“备忘录方法”改进的斐波那契数列的递归算法如表4所示（注：定义全局数组a，初始值将a[1]，a[2]设为1，其他元素设为0）。

经过深入分析，进一步得出如下结论。虽然表4中的“备忘录方法”可以使得递归算法中的子问题计算次数减少至n，但其递归调用次数没有得到改变。因此，我们还可以对上述算法进一步改进，以减少递归调用次数，其基本思路是在调用递归函数时，首先检查是否以保存小问题的解。由此，得到如表5所示的较完美的递归算法，虽然该算法的被调用次数仍大于n（经分析，被调用次数约为n的2倍）。

通过上述3个递推方程的算法设计、分析与优化，我们可得出对于递推方程的两种动态规划算法解决方案：一种称为“备忘录方法”的基于递归算法解决方案，其存在设计简单但效率较低的特点;一种为基于迭代算法的解决方案，其通过存储小问题的解逐步构造和计算大问题的解，具有高效的优点。

（四）递推方程的构建与算法设计

采用启发式策略与学生一起寻找上述问题1和问题2的递推方程，并依据上述知识进行算法设计、分析和优化。构造最优化问题的递推方程的关键是确定大问题的最优解与其包含的某个或某些小问题的最优解之间的关系。因此，如何用符号描述某个子问题的最优解是构建递推方程的前提。我们将引导学生采用试探方法描述子问题的最优解及其之间的递推方程。例如，针对问题1，我们用F（i）表示n个元素中前i个元素所构成的子问题的最优解所对应的目标值，即，如何选择前i个元素中的某些不相邻的数，使得这些数的和最大，该和就是F（i）的值。显然，原问题的优化目标可表示为F（n），而F（1）显然就是a[1]的值。对于选择问题的常见的递推方程的构建方法是考虑是否选择了某个数，在此问题中，可考虑F（i）的最优解中是否包括第i个元素。分析可知：（1）如果最优解中包括第i个元素，那么将导致其相邻的左侧（即第i-1个）元素不能被选取，此时，F（i）=a[i]+F（i-2），即前i-2个元素构成的子问题的最优解加上第i个元素就是前i个元素构成的子问题的最优解;（2）反之，如果不包括第i个元素，那么其相邻的左侧的第i-1元素可以被选取，因此，前i个元素构成的子问题的最优解就等于前i-1个元素构成的子问题的最优解。由于第i个元素是否在F（i）中只存在两种情况，因此，可得出F（i）的如下递推方程：

在此基础上，可设计上述递推方程的递归算法和迭代算法，如表6所示。

经过分析，可知基于迭代算法的时间和空间复杂度均为O（n），而基于递归的算法可采用备忘录方法进一步改进，改进后的时间复杂度仍为O（n），但效率较低。

在此基础上，启发学生根据优化目标的计算过程寻找对应的最优解。需要强调的是，动态规划的迭代算法的设计采用“自下而上计算最优解的目标值、自上而下寻找最优目标对应的最优解”思想。所谓“自下而上”是指通过小问题的最优解计算大问题的最优解，而“自上而下”是指通过大问题的最优解寻找小问题的最优解。对于问题1，最终的最优解存储在v[n]中，而根据表6的迭代算法可知，v[n]的计算是通过比较a[j]+v[j-2]和v[j-1]的大小得到的，因此，通过构建一个循环可得出最优解所包含的元素，其对应的伪代码如表7所示，数组x中等于1的元素的下标所对应的元素就是被选择的元素。

问题2的递推方程的构建过程较上述问题复杂一些。我们将首先尝试简单的解决方案，在发现问题的基础上，寻找正确的递推方程。具体过程包括：首先，以F（i）表示在不超过背包容量B的前提下，选择前i个物品中的某些物品（i？燮n）所得到的最大价值，即F（i）对应的子问题是由前i个物品及容量为B的背包构成的。然后，分析F（i）所对应的最优解中是否包括第i个物品，根据前文叙述，初步构造的F（i）递推方程为：

但是，上述递推方程的第3个公式是错误的。因为F（i-1）显然小于F（i-1）+v[i]，这意味着在第i个物品的重量不超过背包容量时，一定会装入背包。导致出现该错误的原因在于，在第i个物品的重量不超过背包容量时，如果选择将该物品装入背包，实际上将导致背包的可用容量变小，即第i个物品的重量将消耗背包的部分容量。但是，上述递推方程并没有考虑背包容量的变化。因此，为解决该问题，应该将背包的容量考虑进去。基于上述考虑，我们以符号F（i，W）表示在不超过背包容量W的前提下，选择前i个物品中的某些物品（i？燮n）所得到的最大价值，即F（i，W）对应的子问题是由前i个物品及容量为W的背包构成的。在此基础上，可构造F（i，W）的正确的递推方程为：

在此基础上，采用二维数组a存储中间結果，可设计上述递推方程的递归算法和迭代算法，如表8所示。

显然，函数F（n，B）将返回原背包问题的最优解对应的价值。在此基础上，可引导学生构造如表9的算法伪代码，以获得背包问题的最优解，其中，数组x中等于1的元素的下标所对应的元素就是被选择的元素。

经过分析，可知基于迭代算法的时间和空间复杂度均为O（n*B）。在此基础上，可继续分析0-1背包问题的动态规划算法的优缺点，并可对算法进行改进，以进一步降低算法的空间复杂度。

三、结束语

本文以培养学生问题解决能力为目标，以算法课程中的动态规划算法教学为例，提出了一种新的教学案例设计思路，以启发式、探究式教学方法，从易到难，逐步解决实际问题，突出训练和培养学生的问题分析与建模能力、递推方程的构建能力、基于递推方程寻找最优解的能力、递推方程的算法设计与编程实现能力、递推方程的算法优化与复杂度分析能力、递推方程的算法实验分析能力。这将为以能力目标导向的算法课程教学改革提供新思路，为培养学生未来职业发展所需问题解决能力提供教学设计案例。

参考文献：

[1]吴劲，周帆，王瑞锦，等.OBE模式下的程序设计与算法基础课程改革探索[J].计算机教育，2019（11）：86-90.

[2]张文宇，刘鹏，陈卫卫，等.面向系统能力培养的计算机专业课程教学评价研究[J].计算机教育，2019（2）：107-111.

[3]李玲.以培养计算思维为导向的高中《算法与程序设计》教学案例设计[D].沈阳师范大学，2016.

[4]王玉柱，张玉清，季晓慧，等.新工科理念下高性能计算导论课程内容与实践教学的探索[J].教育教学论坛，2019（25）：97-98.

[5]王晓东.计算机算法设计与分析（第4版）[M].电子工业出版社，2012.