宛 楠 （皖南医学院计算机教研室，安徽 芜湖241000）

张 义 （安徽工程大学计算机与信息学院，安徽 芜湖241000）

ACM国际大学生程序设计竞赛 （简称ACM／ICPC）是由国际计算机界历史悠久、颇具权威性的组织ACM学会 （Association for Computer Machinery）主办，是世界上公认的规模最大、水平最高的国际大学生程序设计竞赛，在信息技术界具有相当的影响力，竞赛的很多题目都是在实际的工程项目应用中遇到的问题，能够比较全面的考察学生对计算机以及其他学科知识的综合运用能力，通过竞赛可以系统的检验学生的计算机编程等方面的综合水平，而这些正是IT从业者所急需的。在竞赛中涉及到各种算法，其中动态规划是较为常见的算法之一［1］。下面，笔者对动态规划算法的进行了分析和研究❶。

1 动态规划算法的基本思想与步骤设计

1）动态规划算法的基本思想 动态规划算法基本思想是将所求解问题分解成若干个子问题，先求解子问题并保存已解决的子问题的答案，然后从这些子问题的解得到原问题的解。

2）动态规划算法步骤设计 动态规划算法适用于解最优化问题，一般可按以下步骤设计动态规划算法：①找出最优解的特质，并描述其结构特征；②用递归的方式定义最优值；③以自下向上的方式计算出最优值；④根据计算最优值时得到的信息，构造最优解。

步骤①～③是动态规划算法的基本步骤。如果只需要求出最优值，则步骤④可以省去。如果从最底层的子问题开始，自底向上地逐一推导出子问题的解，则编程的时候可不写递归函数［2］。……