Posts

introduce 动态规划是通过组合子问题的解来解决整个问题，不同与分治算法，动态规划的子问题不是相互独立的， 动态规划通过对每个子子问题只计算一次来优化计算过程。 动态规划一般用于最优化问题求解. 一般步骤 描述最优解结构 递归定义最优化解的值, 定义递归式(最重要的一部) 按自底向上的方式计算最优解 构造一个最优解(一般不需要，或第三部已经保留了过程) 能应用动态规划的两个主要特征 问题包含最优子结构,父问题的最优解需要子问题的最优解 子问题重叠，应用动态规划可以提高性能 动态规划的变形: 备忘 自顶向下的计算策略. 使用低效但是容易理解的递归算法，同时对子问题解进行缓存。 TODO实例1: 生产线问题 TODO实例2: 矩阵乘法 TODO实例3: 最长公共子序列 TODO实例4: 编辑距离