动态规划#

虽然初中的时候搞oi学C的时候也学完了算法，但是那么久没用了，思想忘得干干净净（）加上Python语法还是很不一样，所以重新学一下所有的算法是很有必要的！(ง •_•)ง

基本思想#

动态规划（Dynamic Programming, DP）

通过把原问题分解为相对简单的子问题，并利用重叠子问题性质来求解复杂问题，这与分治法有相似之处（不知道，我看别人这么写）。与分治法不同的是，动态规划经分解后得到的子问题往往不是相互独立的。
通常用于求解某种具有最优性质的问题。在这类问题中，可能会有许多可行解，每一个解都对应一个值，我们希望找到具有最优值的解。

可以看出来，动态规划并不是某种具体的算法，没有具体的类型模板，而是一种解决特定问题的方法，只能通过做题总结经验。

引入：取代递归#

递归时间复杂度很高，动态规划就能通过记录之前搜索过的状态减少时间复杂度。

eg.爬楼梯问题

假设楼梯有n级，想象一下，你正在爬楼梯，每次可以爬1级或2级。问题是：有多少种不同的方法可以爬到楼梯的顶部？

分析：可以有两种选择：
1. 从 n-1 阶楼梯爬 1 阶上来
2. 从 n-2 阶楼梯爬 2 阶上来

定义f(n)表示n阶楼梯总共的方法数。可以总结出：f(n) = f(n-1) + f(n-2)

初始条件

n = 1: f(1)=1;n = 2: f(2)=2

经过迭代，就可以得到f(n)的值
编程实现
1. 递归
```
def stairs(n):
  if n == 1:
      return 1
  elif n == 2:
      return 2
  else:
      return stairs(n - 1) + stairs(n - 2)
```
但是，调试着玩的时候就可能会出现：
```
RecursionError: maximum recursion depth exceeded while calling a Python object
```
原因：Python默认递归调用深度为1000（即最多递归调用1000次），也就是说n稍微大一点就会炸。虽然可以使用sys修改默认的递归深度，但是治标不治本。并且亲测，输入45就等了很久没出结果，考场上肯定是不敢用的。
1. 动态规划
用一个“数组”保存已解决的子问题的答案，而在需要的时候再从数组中查找出已求得子问题的答案，这样就可以避免大量的重复计算。在Python中，“数组”我们用的是列表。
首先我们来看一句代码（别问为什么看，问就是我发现自己不会这么写）：
```
dp=[0]*(n+1)
```
这行代码可以创建一个名为dp列表，列表中的元素个数为n+1，初始化所有元素都为0。
下面我们来改写一下之前的代码！
```
def stairs(n):
  if n == 1:
      return 1
  elif n == 2:
      return 2
  else:
      dp = [0] * (n + 1)
      dp[1] = 1
      dp[2] = 2
      for i in range(3, n + 1):
          dp[i] = dp[i - 1] + dp[i - 2]
      return dp[n]
```

现在输入100，结果生成也很快，大大减少了时间复杂度。

动态规划原理#

用动态规划解题需要满足三个条件：

最优子结构

问题的最优解包含子问题的最优解，反过来说，子问题的最优解可以推出问题的最优解。放在动态规划中，就是说前一阶段的状态可以通过转换方程推出后一阶段的状态。

具有最优子结构也可能是适合用贪心的方法求解，并且最有子结构的证明往往是复杂的，所以动态规划就是很难啊啊啊啊。

无后效性
已经求解的子问题，不会再受到后续决策的影响。
子问题重叠
跟前面的操作一致，重复的子问题可以记录下结果，避免重复计算。

动态规划的基本思路#

将原问题划分为若干阶段，每个阶段对应若干个子问题，提取这些子问题的特征（状态），分析最优子结构性质；
寻找各状态间的相互转移方式（状态转移方程）；
按顺序求解每一个阶段的问题。

例题分析：最长公共子序列#

给定一个长度为 n 的序列 A 和一个长度为 m 的序列 B(n,m <= 5000)，求出一个最长的序列，使得该序列既是 A 的子序列，也是 B 的子序列。

要注意子序列的定义：只考虑相对位置，并不一定要在字符串中相邻。例如字符串advgrkd，agk也是字符串的子序列

分析题目
设状态f(n,m)表示A、B的最长子序列，n、m表示A中(0,n)的子串，m表示B中(0,n)的子串。
我们考虑A、B的最后一个元素：设为x与y
如果x==y：显然，f(n,m) = f(n - 1,m - 1) + 1
如果x!=y：可能存在三种情况：
a.x存在于B中最长子序列的后面，最长子序列拉长了，f(n,m) = f(n,m - 1) = f(n - 1,m - 1) + 1
同时有 f(n,m - 1) > f(n - 1,m)
b.y存在于A中最长子序列的后面，最长子序列拉长了，f(n,m) = f(n - 1,m) = f(n - 1,m - 1) + 1
同时有 f(n,m - 1) < f(n - 1,m)
c.x、y不影响最长子序列的长度，f(n,m) = f(n - 1,m) = f(n,m - 1) = f(n - 1,m - 1)
因此可以得出：f(n,m)=max{f(n - 1,m),f(n,m - 1)}
从这里也可以得到递归结构。
初始化问题
在遇到第一个相同的之前，没有最长子序列，因此设置为0就行。
子序列求解
最终f(n,m)为子序列的长度，那么子序列如何求解呢？由于前面我们是从结尾开始讨论，现在我们也从结尾开始思考：假设最长子系列为line。
如果x==y：显然，line += x 或 line += y。
如果x!=y：可能存在三种情况：
a.f(n,m) = f(n,m - 1) = f(n - 1,m - 1) + 1，也就是 f(n,m - 1) > f(n - 1,m)时，x存在于B中最长子序列的后面。
我们下一步会让x加入line中，那就让下标m递减，直到结尾的字符等于x；
b.f(n,m) = f(n - 1,m) = f(n - 1,m - 1) + 1，也就是 f(n,m - 1) < f(n - 1,m)时，y存在于A中最长子序列的后面
我们下一步会y加入line中，那就让下标n递减，直到结尾的字符等于y；
c.f(n,m) = f(n - 1,m) = f(n,m - 1) = f(n - 1,m - 1)，x、y都不在子序列中，则下标都递减。

具体代码实现

这又开辟出了本人的知识盲点（）C语言中有二维数组，那么Python中有什么呢？

答案就是：二维列表（(^_^)医学你到底教了什么）。

我们来看一行代码：

dp = [[0] * (n + 1) for _ in range(m + 1)]

可以理解为：对于每个 m + 1 中的数字，创建一个长度为 n + 1 的列表，并将每个元素初始化为0。由此就构造了一个 m + 1 行， n + 1 列的二维列表，其中每个元素都被初始化为0。

访问每个元素的方式和C语言也相同。

由此写代码如下：

import sys
def sequence(n,m):
    dp =  [[0] * (m+1) for _ in range(n + 1)]
    for i in range(1, n+1):
        for j in range(1, m+1):
            if a[i-1]==b[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    line = ""
    i=n
    j=m
    while i>0 and j>0:
        if a[i-1]==b[j-1]:
            line += a[i-1]
            i-=1
            j-=1
        elif dp[i-1][j]>dp[i][j-1]:
            i-=1
        elif dp[i-1][j]<dp[i][j-1]:
            j-=1
        else:
            i-=1
            j-=1
    return line

input = lambda: sys.stdin.readline().strip()
a, b = input(), input()
n = len(a)
m = len(b)
Str=sequence(n,m)
reversed_s=Str[::-1]  #也可以修改元素进入line的方式
print(reversed_s)

测试输入：

AYGKBRDJ
GESCTBLIFRJV

得到输出：

GBRJ

动态规划有多种题型，像背包dp、线性dp、记忆性搜素等等，之后再进入更深入的学习！:)