Dynamic Programming(2)

可以用动态规划解决的几个常见问题：

---

• 组合问题中的动态规划：
  
  1. 0-1背包问题；
  2. 最长公共子序列(包括连续的和非连续的两种，都可以用DP做，不过连续的用suffix tree做可以达到O(n)的时间复杂度)；
  3. 最大子段和问题，即求一个数列中和为最大的一个连续子段(DP需要O(n)就可以解决，brute force最少要O(n^2), 分治要O(nlgn)，DP费时最短)；
  4. 硬币找换问题
  
  
• 图问题中有：
  1. TSP问题(travelling salesman problem)：旅行n个城市，要求各个城市经历且仅经历一次，然后回到出发城市，要求所走的路程最短；
  2. 多段图的最短路径
  
  
• 查找问题：
  1. 最优二叉查找树(注意与Hofmann编码树区别开)；
  2. 近似串匹配问题
  
  
• 其他：
  1. 装配线调度问题；
  2. 矩阵连乘法问题
  
  

     【注：学习DP，《算法导论》和《算法设计与分析》都是不错的教材。】
     其实能用DP解决的问题很多都可以用回朔剪枝或分治解决。