分治法、贪心法、动态规划的思想

分治法将一个规模为n的问题分解为K个规模较小的子问题，这些子问题互相独立且与原问题相同。逢归的解决这些问题，然后将各个子问题的解合并得到原问题的解。

贪心法的基本思想是当前的选择可能要依赖于已经做出的选择，但不依赖于有待于做出的选择和子问题。因此贪心法是自顶向下，一步一步地做出贪心的选择。

动态规划的实质是分治思想和解决冗余，因此动态规划是一种将问题实例分析为更小的、相似的子问题，并存储子问题的解而避免计算重复的子问题，以解决最优化问题的算法策略。

动态规划所针对的问题有一个显著的特征，即它对应的子问题树中的子问题呈现大量的重复。动态规划的关键在于，对于重复的子问题，只在第一次遇到时求解，并把答案保存起来，让以后再遇到时直接引用，不必重新求解。