1 第6章 动态规划法 教学内容 动态规划的定义及历史 动态规划求解问题的步骤 动态规划计算二项式系数 图问题中的动态规划法 组合问题中的动态规划法 组合问题中的动态规划法 要求 掌握动态规划的思想及文体求解步骤，掌握动 态规划求解常见问题如：每对节点间的最短距 离、最优二分检索树、背包问题等中的应用。第6章动态规划法 6.5实验项目最大子段和问题 6.4查找问题中的动态规划法 6.3组合问题中的动态规划法 6.1概述 6.2图问题中的动态规划法6.1 概 述 6.1.1最优化问题 6.1.2最优性原理 6.1.3动态规划法的设计思想约束条件：有n个输入，它的解由这n个输入的一个子集组成 ，这个子集必须满足某些事先给定的条件，这些条件称为约束 条件 可行解：满足约束条件的解称为问题的可行解 目标函数：满足约束条件的可行解可能不只一个，为了衡量 这些可行解的优劣，事先给出一定的标准，这些标准通常以函 数的形式给出，这些标准函数称为目标函数 最优解：使目标函数取得极值（极大或极小）的可行解称为最 优解 最优化问题：这类问题就称为最优化问题 6.1.1最优化问题 什么是最优化问题？例：自动柜
