动态规划法的教学引例——数字三角形问题

张惠艳，陈芳

(淮阴师范学院，江苏淮安 223300)

1 引言

动态规划[1](Dynamic Programming 简称DP)是解决“多阶段决策问题”的一种高效算法。通过合理组合子问题的解从而解决整个问题解的一种算法。其中子问题并不是独立的，这些子问题又包含有公共的子子问题。动态规划算法就是对每个子问题只求一次，并将其结果保存在一张表中(数组)，以后再用到时直接从表中拿过来使用，避免重复计算相同的子问题。“不做无用功”的求解模式，大大提高了程序的效率。动态规划算法常用于解决统计类问题(统计方案总数)和最优值问题(最大值或最小值)，尤其普遍用于最优化问题。动态规划算法能解决的问题主要分为线性型(如最长公共子序列)，坐标型(如多段图问题，数字三角形)，区间型(如矩阵连乘)，背包型(如0-1 背包问题)，树型(如选课问题)等。传统讲解方法都是直接用经典例题背包问题[2]，不便于初学者理解重复子问题的产生、解决方法，以及动态规划法的设计策略。

数字三角形问题曾是国际信息学(计算机)奥林匹克竞赛的试题，这一问题可采用深度优先搜索算法，记忆化搜索算法，以及动态规划法的方法来设计解决，可作为算法设计与分析课程中动态规划法这一章内容的引例纳入课程中讲解。通过该例的三种不同算法设计的讲解以及路径的追踪可以让学生深刻体会深度优先搜索算法递归解决该问题存在重复的子问题，大大降低了算法的效率；为了解决重复的子问题，提出了记忆化搜索算法，减少重复的子问题的求解，提高算法效率；进一步分析发现数字三角形问题有明显的阶段性，可用表记录子问题的解，以后可以直接使用，非常自然地过渡到动态规划的讲解，提出动态规划法的备忘录和路径追踪。所以此问题非常适合动态规划法教学的引例，便于学生理解该法的设计思想和适用问题，为动态规划法的教学做铺垫。采用典型实例教学[3]，将复杂抽象算法理论与简单的典型实例有机结合，这样使学生由被动学习变为主动学习，培养学生对算法学习的兴趣。同一问题的不同算法实现，对于提升学生的逻辑思维能力和编程解决实际问题的能力也有着非常重要的意义[4-5]，能为学生进一步分析和解决计算机科学与技术领域的复杂工程问题奠定良好基础。

2 问题描述

有一个数字三角形，从最顶层出发，每一步只能向左下或右下方向走。编程求从最顶层到最底层的一条路所经过位置上的数字之和的最大值。输入样例如图1、图2所示，为方便讲解，用图2向正下或右下方向走。输出：一个正整数，路径上数字之和的最大值。

图1 输入样式1

图2 输入样式2

3 算法设计

3.1 深度优先搜索算法

深度优先搜索(缩写DFS)是对一个连通图进行遍历的算法。它的思想是从一个顶点V0开始，沿着一条路一直走到底，这种尽量往深处走的概念即是深度优先的概念。从数字三角形的第一个顶点向左下或右下方向一直走到最后一行的结点的过程就是深度优先搜索，图1、图2的图形可以理解为只是形状不同，都可以采用二维数组a[Max][Max]存储，Max 是数字三角形的行数，可在程序的开头用const int 进行定义。当前结点的坐标记为(i,j),左下方结点的坐标可以标记为(i+1,j)，右下方结点的坐标可以标记为(i+1,j+1)。数字三角形问题的深度优先搜索算法的C++代码可写为：

深度优先搜索算法必然要递归实现，通过递归调用分析可知，若是10行的数字三角形，如图3，每个子问题被递归调用的次数如图4，10 行数字三角形中子问题调用最多的次数将达126次，这种算法设计方法大大降低了求解问题的效率，需要改进算法，提高效率。

图3 10行的数字三角型

图4 子问题被递归调用次数

3.2 记忆化搜索算法

记忆化搜索是在递归的过程中，将已经计算出来的结果保存起来，之后再次用到时直接取出结果，避免重复运算，可提高算法的效率。用二维数组a 记录数字三角形，二维数组f 保存数字三角形中已经计算出来的结点值，记忆化搜索算法的C++代码为：

数组f的元素初始化-1，数组大小等同于数组a。记忆化搜索算法可使数字三角形每个子问题仅被计算一次，大大提高了算法的效率。若是10 行的数字三角形，如图3，每个子问题被递归调用的次数如图5，10行数字三角形中每个子问题最多被调用一次，所以算法的时间复杂度为Ο(n2)。

图5 记忆化搜索算法下子问题被递归调用次数

因为存储每一次计算的结果，需要一个跟原数字三角形一样大小的二维数组，牺牲了空间。既然已经牺牲了空间，能否进一步提高效率，消除递归？动态规划法可消除递归，而且可追踪出得到最大值的路径，如图1的最大值为30，路径：7-＞3-＞8-＞7-＞5。

3.3 动态规划法

数字三角形的递归求解存在重复的子问题，用表记录子问题的解，以后可以直接使用。在求解最值的过程中，将三角形的每一行看成一个阶段，因此有明显的阶段性，这是典型的坐标型问题，可采用动态规划算法求解。对坐标型问题动态规划法通常都有正推和倒推两种实现方法。

正推：从a[0][0]出发，按照向下或右下方向一直走到最后一行，依次计算f[i][j]的值，递推方程：f[i,j]=max(f[i-1,j-1],f[i-1,j])+a[i,j]，因为第一列从第二个元素开始只能用其正上方的元素求得，从第二行开始的对角线的元素只能由其斜上方的元素求得，因此递推方程不适用边界值，边界值要单独处理。问题的解需在二维数组f 的最后一行中求最大值，其C++实现代码如下：

倒推：从数组a 的最后一行出发，将最后一行先赋给数组f的对应元素，按照向上或左上方向一直倒推到第一行，依次计算f[i][j]的值，递推方程：f[i,j]=max(f[i+1,j],f[i+1,j+1])+a[i,j]，f[0][0]即是问题的解，其C++代码如下：

动态规划法让每个结点值只求解一次，时间复杂度仍为Ο(n2)，但消除了递归，大大改进了算法的效率。

4 路径追踪

动态规划法求解问题不仅可以得到问题的解，还可以追踪解的路径。以顺推法为例，在求解备忘录f的过程中，增加标记数组m来记录解是如何得到的，可以根据数组m来追踪问题的解。其C++实现代码如下：

5 结束语

数字三角形问题可采用不同的算法进行设计，不同的算法思想有不同的实现方法，不同的算法效率。在算法设计与分析课程中，建议在讲解动态规划法这一章节前加入这一引例，可以让学生体会不同算法设计的思想，还可自然地过渡到动态规划法求解问题的精髓——备忘录和标记函数，激发学生对算法学习的兴趣。最终为学生以高效的算法解决实际应用问题打下良好基础[5]。