【简识】认识动态规划

动态规划相信大家都知道，动态规划算法也是新手在刚接触算法设计时很苦恼的问题，有时候觉得难以理解，但是真正理解之后，就会觉得动态规划其实并没有想象中那么难。网上也有很多关于讲解动态规划的文章，大多都是叙述概念，讲解原理，让人觉得晦涩难懂，即使一时间看懂了，发现当自己做题的时候又会觉得无所适从。我觉得，理解算法最重要的还是在于练习，只有通过自己练习，才可以更快地提升。所以我们来看几个例题，这样我们才能更好地认识动态规划，更好地理解和运用动态规划。
现在我们来看一个例题：
最长递增子序列
既然是动态规划法，那么最重要的自然就是寻找子问题，对于这个问题，我们找到他的子问题：对于长度为N的数组A[N] = {a0, a1, a2, …, an-1}，假设假设我们想求以aj结尾的最大递增子序列长度，设为L[j]，那么L[j] = max(L[i]) + 1, where i < j && a[i] < a[j], 也就是i的范围是0到j - 1。这样，想求aj结尾的最大递增子序列的长度，我们就需要遍历j之前的所有位置i（0到j-1），找出a[i] < a[j]，计算这些i中，能产生最大L[i]的i，之后就可以求出L[j]。之后我对每一个A[N]中的元素都计算以他们各自结尾的最大递增子序列的长度，这些长度的最大值，就是我们要求的问题——数组A的最大递增子序列。时间复杂度：由于每一次都要与之前的所有i做比较，这样时间复杂度为O(N^2)。
显然，这是一个非常低效的方法，因为其中有大量的重复计算。并且不满足动态规划的第二个特点：“所有的子问题都只需要解决一次“。
所以我要在这里引入一个新的想法：备忘录法
即，在计算中将之前计算过的结果保存下来，待到想用的时候再提出来调用。也就是相同的计算过程只计算一次，而后再碰到相同的过程，可以利用之前得出结果，这样我们就省下了好多的计算过程，也就省下了运算量，让时间复杂度变得更简单。

这样我们可以将一个题的复杂计算转化为简单计算，而重复的简单计算只计算一次，再循环利用，一道题就这么轻松地解决了，还省下了计算量。