五大算法思想

设计思想：将一个难以直接解决的大问题分解成规模较小的相同问题，以便分而治之。 实际的应用：快速排序、归并排序 分治法在每一层递归上的基本步骤： ①　分解：将原问题分解为若干个规模较小、相互独立、与原问题形式相同的子问题。 ②　解决：若子问题规模较小就直接解决，不然就递归解决各个子问题 ③　合并：将各个子问题的解合并为原问题的解

2. 动态规划法

设计思想：最优化原理，即一个过程的最优决策具有这样的性质：即无论其初始状态和初始决策如何，其今后诸策略对以第一个决策所形成的状态作为初始状态的过程而言，必须构成最优策略 动态规划法所要满足的条件： ①　问题中的状态满足最优化原理 ②　问题中的状态必须满足无后效性，无后效性指的是下一时刻的状态只与当前的状态 有关而与当前状态的之前状态无关。 动态规划三要素： ①　问题的阶段 ②　每个阶段的状态 ③　从前一个阶段转换到后一个阶段的递推关系 实际的应用：0/1背包问题 最长公共子串问题