转自Matrix67的博客《什么是P问题、NP问题和NPC问题》。这或许是众多OIer最大的误区之一。你会经常看到网上出现“这怎么做，这不是NP问题吗”、“这个只有搜了，这已经被证明是NP问题了”之类的话。你要知道，大多数人此时所说的NP问题其实都是指的NPC问题。他们没有搞清楚NP问题和NPC问题的概念。

贪心算法通常是自顶向下设计的。也需要具有最优子结构。贪心算法也是一种启发式算法，并不能一定保证是最优解。从动态规划到贪心算法的转化中，我们通常经理如下步骤：……

来自：https://blog.csdn.net/so_geili/article/details/53353593 版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。

分治算法的三个步骤：分开-解决-合并

动态规划和分治算法的区别在于，分治算法将问题分成不重叠的几个子问题，分别求解；而动态规划的子问题是重叠的，每次求解子问题后会把子问题保存起来（例如表格），避免了重复计算。