步骤 将问题表示成多步判断 ■确定是否满足最优子结构性质—一必要条件 确定子问题的重叠性——估计算法效率 列出关于优化函数的递推方程(或不等式)和边 界条件 自底向上计算子问题的优化函数值--递归 的算法 备忘录方法记录中间结果 标记函数追踪问题的解
步骤 将问题表示成多步判断 确定是否满足最优子结构性质——必要条件 确定子问题的重叠性——估计算法效率 列出关于优化函数的递推方程(或不等式)和边 界条件 自底向上计算子问题的优化函数值----非递归 的算法 备忘录方法记录中间结果 标记函数追踪问题的解
常见的实现形式 自底向上—递推 通过递推公式由小问题得到大问题的解,状态 就是递推公式的每个中间结果。 ■自顶向下—一备忘录 建立一个全局可以访问的状态表,把递归搜索 的结果保存起来,当下次达到状态时直接返回 结果。 第一种形式的程序更快更省空间 第二种形式有时候更直观,有助于理解
常见的实现形式 自底向上——递推 通过递推公式由小问题得到大问题的解，状态 就是递推公式的每个中间结果。 自顶向下——备忘录 建立一个全局可以访问的状态表，把递归搜索 的结果保存起来，当下次达到状态时直接返回 结果。 第一种形式的程序更快更省空间 第二种形式有时候更直观，有助于理解
搜索,备忘录,递推 搜索的方法 函数 shortPath返回一个节点到目标节点的最小路径 长度 shortPath(node) min inf. forG=i child begin o:j!= i.child. endo:++] t= shortPath j) if (t+ length(node, * j< min) min =t+ length(node, j; return min
搜索，备忘录，递推 搜索的方法 函数shortPath返回一个节点到目标节点的最小路径 长度 shortPath(node) { min = INF; for(j = i.child.begin(); j != i.child.end(); ++j) { t = shortPath(*j); if (t + length(node,*j) < min) min = t + length(node,*j) ; } return min; }