《高级算法与数据结构》课程思政教学案例（一等奖）

《高级算法与数据结构》课程思政教学案例（一等奖）

一、授课内容

1.1动态规划算法的基本思想

在现实生活中，有一类问题被定义为最优决策问题，这类问题

可能会有许多可行解，每一个解都对应于一个值，我们希望找到具有

最优值的那个解，即最优解。20世纪40年代，RichardBellman首

次使用了动态规划这个术语，用来描述最优决策问题的求解过程。其

核心思想是将最优决策问题按照时间或空间特征分解成若干相互关

联的阶段，以便按次序去求每个阶段的解。各阶段开始时具有客观条

件（称之为状态），当各阶段的状态确定以后，就可以做出不同的决

定，从而确定下一阶段的状态，这种决定称为决策。“动态”是指在

一定条件下，根据上一阶段的状态和决策来导出本阶段的状态，“规

划”是指建立状态转移方程。最优决策问题的难点在于，各个阶段决

策的选取不能任意确定，它既依赖于当前面临的状态，又影响着以后

的发展。

1.2动态规划算法与分治法的区别和联系

动态规划算法与（第二章）分治法类似，都是将待求解问题分

解为若干个子问题，先求解子问题，再结合这些子问题的解得到原问

题的解。与分治法不同之处在于：

（1）适合用动态规划求解的问题经分解得到的子问题往往不是

相互独立的（即重叠子问题），在递归模型上采用分治法自顶向下求

解时，有些子问题被反复计算。动态规划算法正是利用重叠子问题的

性质，将各阶段子问题的最优值保存在一个表格中，在需要时以常数

时间查看结果，这样可以避免大量的重复计算。对于一些在递归模型

上具有指数下界的算法来说，当不同子问题的个数随问题的大小呈多

项式增长时，用动态规划的表格式方法来存储重叠子问题的解，可以

将指数时间减少为多项式时间，从而有效降低了时间复杂度。

（2）每个阶段的子问题可能会有许多可行解，当问题的最优解包

含了其子问题的最优解时（即最优子结构），表格里只存储子问题的

最优解就可以了。利用最优子结构性质，动态规划可以自底向上的从

子问题的最优解逐步构造出原问题的最优解，从而有效控制了空间复

杂度。

1.30T背包问题的动态规划算法

0-1背包问题是指，给定n种物品和一个背包，物品i的重量为

wi,价值为vi,背包的容量为S,问如何选择装入背包中的物品，使

得背包中物品的总价值最大。利用动态规划算法求解该问题的思想是,

先逐步解决容量为1,2,…的小背包问题，最后解决容量为S的背包

问题。

从动态规划的基本性质为切入点，分别证明0T背包问题具有最

优子结构性质和重叠子问题性质，而后由浅入深地分析初始阶段、终

止阶段及各阶段的问题空间，在此基础上递归定义状态变量（即最优

值）及其状态转移方程。接下来，对于给定的问题实例，以自底向上

的方式计算最优值，最后根据计算最优值时得到的信息、，调用递归模

型通过回溯的方式构造最优解。

二、实施过程

（一）思政元素类型：

社会主义核心价值观教育，职业理想和职业道德教育。

（二）课堂教学方法：

1.教学手段：采用板书、PPT、动画、视频等多媒体形式。

2.课程思政融入点：知识点中的动态规划基本原理与“知行合

一”哲学思想、“舍与得”的哲理、适中思想等相契合，从而引申出

思政案例。

三、思政元素内容

元素一：动态规划中的“知行合一”理念

（-）元素内容

能够采用动态规划算法来求解的问题需要具备两个重要性质：

最优子结构、重叠子问题。对于给定问题，只有证明其具备了这两个

性质，才能设计相应的状态转移方程，从而保证动态规划算法的正确

性。这个过程中所体现的是“知行合一”的哲学思想，给出问题具备

最优子结构和重叠子问题性质的定理是“知”，自底向上求解各阶段

子问题的最优值是“行”。由于对问题性质的证明过程涉及数学归纳

法、反证法等，对学生的抽象思维、逻辑思维有一定的要求，因此同

学们往往会忽略对“知”的关注，而把动态规划算法仅仅等同于用伪

代码描述过程，或者直接通过编写程序来运行算法等“行”的范畴,

从而割裂了“知”与“行”之间的关系。

“知行”是中国传统哲学的重要范畴，其始于《尚书》与《左

传》，《尚书》有“非知之艰，行之惟艰”之说［1］,《左传》有“非

知之实难，将在行之”之说［2］。东北大学校训“自强不息、知行合

一”中的“知行合一”出自于《传习录》［3］,它是明代著名哲学家

王守仁的弟子们记录老师的学术讲话及论学书信的集子。守仁说：

“知之真切笃行处即是行，行之明觉精察处即是知。”又说：“若会

得时，只说一个知已自有行在，只说一个行已自有知在。”都是说明

知行本来合一，无可分割。对于知而不行的时弊，王守仁有这样一段

一针见血的话：“今人却将知行分作两件去做，以为必先知了，然后

能行，我如今且去讲习讨论做知的功夫，待知得真了方去做行的功夫,

故遂终身不行，亦遂终身不知。此不是小病痛，其来已非一日矣。某

今说个知行合一，正是对病的药。又不是某凿空杜撰，知行本体原是

如此。”他认为，“真知即所以为行，不行不足谓之知”，又强调“圣

学只是一个功夫，知行不可分作两事”。

理解了“知行合一”的哲学思想，就会将动态规划算法的正确

性证明和算法设计思想有机融合在一起，不可分割。

（二）价值拓展

我们在生活中经常会遇到复杂的最优决策问题，要学会应用“知

行合一”的哲学思想，分析思考问题的性质（即致“知”）和实际去

解决问题（即格“物”）不可分割，“知是行之始，行