分治策略&动态规划

这期我从分治策略和动态规划两个角度出发来比较两种算法的异同点，同时分析常见的递归优化方案，包括记忆化搜索和尾递归， 然后引出动态规划是解决某些问题的最优方法。

概念

开始前先介绍几个概念：

• 自顶向下，理解为从问题的终点向问题的起点解决
• 自底向上，理解为从问题的起点向问题的终点解决
• 最优子结构：当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质
• 重叠子问题：在用递归算法自顶向下解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次