陈晓梅 张晶

摘要：在动态规划算法的教学中，学生最迷惑的是递归公式的建立与“翻译”。并不以单一个具体的事例来讨论动态规划算法的实现，而是利用若干个各具代表性的实例来抽象出动态规划算法的共性以及解题方法。

关键词：动态规划；递归公式；备忘录；自底向上

中图分类号：O221.3 文献标识码：A 文章编号：1009-3044（2018）26-0146-02

1 概述

有一类问题，可以将待求解的问题分解成若干子问题，先求解子问题的解，然后通过这些子问题的解来求得原问题的解。若分解的子问题出现重叠，如果使用常规的递归方法来设计算法，则会耗费大量时间重复计算相同的子问题。而动态规划使用备忘录或自底向上的方法来设计算法，以保证每个子问题最多只被计算一次。

本文基于动态规划求解问题的共性思维探讨动态规划算法的教学过程。

2 动态规划算法案例选择

在动态规划算法的教学中，可以选择一些经典的、代表性强的案例进行教学。使用动态规划解决问题，关键是要确定某个状态的最优解，因此状态的选择是否正确，决定整个问题求解的正确性。一般可选择以第i时刻为起点、第j时刻为终点的状态，如矩阵连乘问题。还可以选择以最小规模子问题或原问题规模为起点、第i时刻为终点的状态，如最长公共子序列问题、最大子段和问题和0-1背包问题。

3 动态规划算法求解问题

动态规划一般用于解最优化问题。利用某个状态（一般是初始状态或目标状态）的最优解去计算下一个状态的最优解，直至获得原问题的全局最优解。……