- 分治算法在每一层递归上的3个步骤：
- 分解。将原问题分解成一系列子问题。
- 求解。递归地求解各子问题。若子问题足够小，则直接求解。
- 合并。将子问题地解合并成原问题的解。
- 动态规划地基本思想
- 从子问题的解得到原问题的解。
- 能够保存已解决的子问题的答案。
- 动态规划可以解得0-1背包问题的最优解。
- 贪心算法无法解得0-1背包问题的最优解。
- 贪心算法可以解得背包问题的最优解。
- 回溯法
- 先判断该节点往下有没有答案。
- 没有，跳过以该结点为根的子树的系统，逐层向祖先结点回溯。
- 有，则进入该子树，继续按深度优先的策略进行搜索。
- 回溯法用于解决n皇后问题。
- 长度为n的字符串的最长公共子序列（LCS）问题，利用动态规划可以有效避免重复计算，取得最优解。时间复杂度为
。
- 在思考两个序列的LCS时，将两个序列各自成环，然后进行判断（即可以首尾连接）。
- 若该问题具有最优子结构和重叠子问题性质，则适合用动态规划。
- 若了解问题的解空间，并以广度优先的方式搜索解空间，则采用的是分支界限算法。
