2021-04-24 自我修养►数据结构与算法►动态规划 动态规划 dp动态规划解决问题通常用于解决最优化问题,通常做出一组选择来达到最优解. 特点 做出每个选择时,通常会生成与原问题形式相同的子问题 多于一个选择子集都会生成相同的子问题(子问题重叠) 关键技术 对每个相同的子问题保存其解,当其重复出现时避免重复求解 通常可将指数时间的算法转换为多项式级别的算法 步骤 刻画一个最优解的结构特征 递归地定义最优解的值 计算最优解的值,通常采用自底向上的方法 利用计算出的信息构造一个最优解 典型问题算法导论钢条切割求两个序列的最长公共子序列构造最优二叉搜索树 Newer 快速排序 Older antlr4实现一个计算器--python语言