动态规划dp

动态规划（Dp）

介绍

动态规划（Dynamic programming）是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。

动态规划问题的特点

1.最优子结构性质：如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质（即满足最优化原理）。最优子结构性质为动态规划算法解决问题提供了重要线索。

2.子问题重叠性质：子问题重叠性质是指在用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，直接从哈希表中获取结果，从而提高效率。

3.无后效性：即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。

例如，若要解一个给定问题，我们需要解其不同部分（即子问题），再合并子问题的解以得出原问题的解。 通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量： 一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。下面我们给出一道简单易懂的例题帮助掌握动态规划。

例题

找出最长的递增子序列的长度

nums=[1,5,2,4,3]

最容易想到的办法就是暴力，我们可以定义一个检索函数，传入起始数，例如从1开始，然后第二个是数可以选5、2、4、3，然后再分别看5的下一位，没有比5更大的了，结束，看2的下一位，可以取4或3，依次遍历，同时记录最长递增子序列的长度。
如图所示为遍历过程

然后用循环依次将各数传入，就可以得到遍历所有起始数的结果了。
虽然这个算法可以得出正确的结果，但当下高标准的需求显然与之不符， 该算法的时间复杂度为O(2**n)*O(n)，指数级别的时间复杂度，在竞赛，考试或者实际应用中都是一个不受待见的存在。

动态规划

我们可以利用动态规划算法对齐进行优化。由上图我们可以发现，暴力算法中存在大量的重复计算，例如在外面遍历子序列1，2，,的时候就已经计算过从4开始的最大子序列的长度，但在后面遍历1，4的时候又一次进行了计算，对此，我们可以在第一次进行计算的时候将结果保存下来，之后遍历到相同的节点就不用再进行重复计算了。
这里采用记录下从i开始的最长的子序列长度从而避免重复计算(下列代码中，定义了列表L来记录)。

#定义一个函数返回其最长的递增子序列
def length_of_LIS(nums):
    n = len(nums)
    L = [1]*n      #定义一个列表存储每个数为起点的最长递增子序列数

    for i in reversed(range(n)):    #从后往前遍历，得到后边每个数为起点的递增子序列长度，当前面的数大于该数时，可直接将将其加上
        for j in range(i+1,n):         #遍历获取以该数为开始的递增子序列长度
            if nums[j]>nums[i]:
                L[i] = max(L[i],L[j]+1)

    return max(L)
nums=[1,5,2,4,3]
print(length_of_LIS(nums))

上述动态规划代码只用了两个for循环，每个循环最多执行n次因此，这段代码的时间复杂度是O(N**2),运行效率大大提高。

动态规划的一般思路

1.暴力（穷举）：首先我们用最朴素的办法根据题目要求写出求解答案的思路（可以用递归等方法先写出来）。
2.记忆化搜索：如果发现过程中有大量重复计算，我们可以通过哈希表将数据记录下来，之后遍历相同节点时直接读取，避免重复计算
3.迭代形式：最后优化代码，改写成为简洁高效的迭代形式。

动态规划灵活性较强，需要勤加练习，相信每一个在黑夜中起舞的人都能迎来耀眼夺目的黎明。

**慢也好，步伐小也罢，是往前走就好。 **—佚名