动态规划的实质就是保存计算过的状态来避免重复计算子问题，去除冗余计算。 动态规划实质上是一种以空间换时间的技术，它在实现的过程中，不得不存储产生过程中的各种 状态，所以它的空间复杂度要大于其它的算法。选择动态规划算法是因为动态规划算法在空间上可以承受，而搜索算法在时间上却无法承受，所以我们舍空间而取时 间。