【概述】

        线性动态规划，是较常见的一类动态规划问题，其是在线性结构上进行状态转移，这类问题不像背包问题、区间DP等有固定的模板。

        线性动态规划的目标函数为特定变量的线性函数，约束是这些变量的线性不等式或等式，目的是求目标函数的最大值或最小值。

        因此，除了少量问题（如：LIS、LCS、LCIS等）有固定的模板外，大部分都要根据实际问题来推导得出答案。

【例题】最长公共子序列(LCS)

lanqiao0J题号1054

lanqiao0J题号1189

 LCS 问题（Longest Common Subsequence），给定一个长度为n数组A和一个长度为m的数组B,求序列的最长公共子序列。

题目描述

输入描述

第一行为第一个字符序列，都是大写字母组成，以 . 结束，长度小于 5000。

第二行为第二个字符序列，都是大写字母组成，以 . 结束，长度小于 5000。

输出描述

第一行输出上述两个最长公共子序列的长度。

第二行输出所有可能出现的最长公共子序列个数，答案可能很大，只要将答案对求余即可。

输入输出样例

输入

ABCBDAB.
BACBBD.

输出

4
7

题目大意：

        一个给定序列的子序列，是在该序列中（不一定连续）删去若干元素后得到的序列。例如:X = {A，B，C，B, D，A， B}，它的子序列有{A， B,C，B,A}、{A，B,D}、{B, C，D，B}等。给定两个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列，最长公共子序列是长度最长的子序列。求两个最长公共子序列的长度和所有可能出现的最长公共子序列个数。

法一：暴力法

先找出A的所有子序列，然后 一 一 验证是否为Y的子序列。
如果A有m个元素，那么A有个子序列（集合的子集的个数），B有n个元素，总复杂度大于

法二：动态规划

dp[i][j]：序列Ai ()和Bj (b1~bj)的最长公共子序列的长度：dp[n][m]
分解为2种情况:
(1)当（当前两个子序列的最后一个相同）时，已求得和的最长公共子序列，在其尾部加上或即可得到的最长公共子序列。状态转移方程:
                                                dp[i]j]= dp[i-1][j-1]+1
(2）当时，求解两个子问题：的最长公共子序列；的最长公共子序列。取最大值，状态转移方程:
                                        dp[i][j]=max{dp[i][j-1], dp[i-1][j]}

复杂度O(nm)

 代码 ：

使用交替滚动数组
(1）当时，状态转移方程：dp[i][i]= dp[i-1][j-1]+1
(2）当时，状态转移方程： dp[i][j]= max{dp[i][j-1], dp[i-1][j]}

n, m = map(int, input().split())
a = [0] + list(map(int, input().split()))  # 从a[1]~a[n]
b = [0] + list(map(int, input().split()))  # 从b[1]~b[n]
dp = [[0] * (m + 1) for _ in range(2)]  # 注意这里是m，不是n
now = 0;  old = 1
for i in range(1, n + 1):now, old = old, nowfor j in range(1, m + 1):if a[i] == b[j]:dp[now][j] = dp[old][j - 1] + 1  else：    # ai≠bjdp[now][j] = max(dp[now][j - 1], dp[old][j])  print(dp[now][m])

 【例题】 最长递增子序列（LIS）

蓝桥骑士lanqi ao0J题号1188

题目描述

小明是蓝桥王国的骑士，他喜欢不断突破自我。这天蓝桥国王给他安排了 N 个对手，他们的战力值分别为 a1​,a2​,...,an​，且按顺序阻挡在小明的前方。对于这些对手小明可以选择挑战，也可以选择避战。身为高傲的骑士，小明从不走回头路，且只愿意挑战战力值越来越高的对手。请你算算小明最多会挑战多少名对手。

输入描述

输入第一行包含一个整数 N，表示对手的个数。

第二行包含 N 个整数 a1​,a2​,...,an​，分别表示对手的战力值。

。

输出描述

输出一行整数表示答案。

输入输出样例

输入

6
1 4 2 2 5 6

输出

4

思路 

LIS：给定一个长度为n的数组，找出一个最长的单调递增子序列。
例:序列A={5,6,7,4,2,8,3}，它最长的单调递增子序列为{5,6,7,8}，长度为4。

做法

定义状态dp[i]：表示以第i个数为结尾的最长递增子序列的长度。
状态转移方程:
                        

最长的单调递增子序列：max {dp[i]}
复杂度： j在0~i之间滑动，复杂度O(n); i的变动范围也是O(n)的;总复杂度。

动态规划:复杂度
本题，DP代码提交到0J会超时。
DP不是LIS问题的最优解法，有复杂度0(nlogn)的非DP解法（二分查找）

本题题解：蓝桥杯刷题026——蓝桥骑士（二分法）

【例题】字符串转换

lanqiao0J题号1507 

题目描述

小蓝拥有两个字符串 S,T​。他希望通过如下操作使得字符 S 转换为字符串 T。

操作有一下三种：

1. 删除一个字符。
2. 插入一个字符。
3. 将一个字符改为另一个字符。

问最少需要操作多少次才可以使得字符串 S 转换为字符串 T。

输入描述

输入第一行包含一个字符串 S。

输入第二行包含一个字符串 T。

1≤∣S∣,∣T∣≤2×10^3，保证 S、T 只包含小写字母。

输出描述

输出一个整数表示答案。

输入输出样例

输入

abc
aa

输出

2

数据范围在：1≤∣S∣,∣T∣≤ ，可以是的复杂度

思路： 编辑距离

把长度m的A存储在数组a[1]~ a[m]，长度为n的B存储在b[1]~ b[n]，不用a[0]和b[0]。

定义状态dp： dp[i][j]表示A的前i个字符转换B的前j个字符所需要的操作次数
操作次数最少：dp[m][n]
下图是A="abcf"，B="bcfe”的状态转移矩阵。

状态转移方程:
(1) 若a[i] = b[j]，则dp[i][j] = dp[i-1][j-1]。例如图中dp[2][1]处的箭头
(2) 其他情况: dp[i][j] = min{dp[i-l][j-1]，dp[i-1][j],dp[i][j-1]} + 1。例如图中dp[4][2]处的箭头。dp[i][j]是它左、左上、上的三个值中的最小值加1，分别对应以下操作:

• dp[i-1][j]+1，删除，将A的最后字符删除:
• dp[i][j-1]+1，插入，在B的最后插入A的最后字符:
• dp[i-1][j-1]+1，替换，将B的最后一个字符替换为A的最后一个字符。

复杂度:O(mn) 

代码：

(1) a[i] = b[j]，则dp[i][j] = dp[i-1][j-1]
(2）其他情况: dp[i][j] = min idp[i-1][j-1], dp[i-1][j], dp[i][j-1]} +1

a = input() ; a = ' '+a   #a[0]不用，用a[1]~a[m]
b = input() ; b = ' '+b
m = len(a)-1
n = len(b)-1
dp = [[0]*(n + 1) for _ in range(m + 1)]
for i in range(1, m+1 ):  dp[i][0] = i  # 初始化
for j in range(1, n+1 ):  dp[0][j] = j  # 初始化
for i in range(1,m+1):for j in range(1, n+1):if a[i]==b[j]: dp[i][j] = dp[i-1][j-1]else:dp[i][j]=min(min(dp[i-1][j], dp[i][j-1]) , dp[i-1][j-1])+1
print(dp[m][n])

【例题】 过河卒

题目描述

如图，A 点有一个过河卒，需要走到目标 B 点。卒行走规则：可以向下、或者向右。同时在棋盘上的 C 点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。

 

例如上图 C 点上的马可以控制 9 个点（图中的P1​，P2​，⋯P8​ 和 C）。卒不能通过对方马的控制点。棋盘用坐标表示，A 点（0，0）（0，0）、B 点（n,m）(1≤n,m ≤ 20)，同样马的位置坐标是需要给出的。0≤马的坐标≤20。

现在要求你计算出卒从 A 点能够到达 B 点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。。

输入描述

一行四个正整数，分别表示 B 点坐标和马的坐标。

输出描述

一个整数，表示所有的路径条数。

输入输出样例

输入

6 6 3 3

输出

6

思路1：模拟

统计路径条数，看起来是个搜索题，可以用DFS求解。把马的控制点标记为不能走，绕过它们。不过，用DFS搜索的路径数量是天文数字，肯定超时。

思路2：网格上的DP

• 在小学上过奥数的都知道，这题应该用“标数法”，就是在每个坐标点上记录能走的路径条数。
• 标数法实际上就是DP的递推。

由于卒只能向下、或者向右移动，所以每个点（i, j）的路径条数等于能走到(i-1, j)的路径条数+能走到上边（i, j-1）的路径条数

定义状态dp[ ][ ]: dp[i][j]表示卒走到坐标(i,j)时能走的路径条数。
如果不考虑马的控制点，有:dp[i]b]= dp[i - 1][j]+ dp[i][j - 1];
也就是(i, j)点的路径条数等于它上面和左边的路径条数之和。这就是小学奥数的“标数法”的原理。
本题的限制条件是马的控制点，只要令控制点的dp[i][j]=0（意思是卒走到该点时能走的路径条数为0）即可，即这个点上无路径。

 代码：

小技巧：把坐标加2，防止马的控制点越界(坐标为负)

dp = [[0]*25 for i in range(25)]
s =[[0]*25 for i in range(25)]
bx,by,mx,my = map(int,input ().split())
bx += 2; by += 2; mx += 2; my += 2  # 把坐标加2
dp[2][1] = 1  # 初始化起始点的上面一点为1        起始点为（2,2）
s[mx][my] = 1;      # 将马的9个控制点设置为1
s[mx-2][my-1]=1; s[mx-2][my+1]=1; s[mx+2][my-1]=1; s[mx+2][my+1]=1;
s[mx-1][my+2]=1; s[mx-1][my-2]=1; s[mx+1][my+2]=1; s[mx+1][my-2]=1;
for i in range(2,bx+1):  # 从（2,2）开始for j in range(2,by+1):if s[i][j]==1: dp[i][j]=0  # 如果是马的控制点，则该点不能走else: dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
print(dp[bx][by]) # 到达终点B的路径条数

【例题】 排队列

2019年国赛题 

题目描述

在一个排列中，一个折点是指排列中的一个元素，它同时小于两边的元素，或者同时大于两边的元素。

对于一个 1 ∼ n 的排列，如果可以将这个排列中包含 t 个折点，则它称为一个 t+1 单调序列。

例如，排列 (1,4,2,3) 是一个 3 单调序列，其中 4 和 2 都是折点。

给定 n 和 k，请问 1 ∼ n 的所有排列中有多少个 k 单调队列？

输入描述

输入一行包含两个整数 n,k (1≤k≤n≤500)。

输出描述

输出一个整数，表示答案。答案可能很大，你可需要输出满足条件的排列数量除以 123456 的余数即可。

输入输出样例

输入

4 2

输出

12

数据范围在1000左右，可以用复杂度为O(n^2)的算法。

方法一：暴力法

20%的测试：1 暴力法:对所有排列进行检查，判断是否为k单调队列。

from itertools import *
n,k = map(int,input().split())
nums = [i for i in range(1, n+1)] # 1~n
cnt = 0
for num in permutations (nums):   # 检查每个排列tmp = 0for i in range(n-2):  # 0 ~ n-3if num[i+1]>num[i+2] and num[i+1]>num[i]:  tmp+=1  # 凸折点elif num[i+1]

N = 520
dp = [[0]*N for i in range(N)]
n,k = map(int,input ().split() )
dp[1][1] = 1
dp[2][1] = 2
for i in range(3, n+1):ki= min(k, i)for j in range (1,ki+1):dp[i][j] += dp[i-1][j]*j + dp[i-1][j-1]*2if j > 1: dp[i][j] += dp[i-1][j-2]*(i-j)
print(dp[n][k] % 123456)

n = int (input ())
w = list (map(int,input ().split() ))
ans = set()  # 用set判重，用来存用多少种答案的
ans.add(w[0])
for i in w[1:]:for j in ans.copy ():  # ans.copy ()浅复制，不会因为该次循环而改变ansans.add(i)                           # 只放新砝码i的质量ans.add(j + i)                       # 将i和答案中每一个数放在同一侧：相加if j - i != 0: ans.add (abs(j - i))  # 将i和答案中每一个数放在不同测：相减
print (len(ans))

n = int(input())
W = list(map(int, input().split()))
s = sum(W)  # 所有砝码之和
dp = [[0] * (s + 1) for _ in range(n)]
for i, w in enumerate(W):  # 初始化：前i个的砝码的质量为wdp[i][w] = 1
for i in range(1, n):  # 第0行不需要管，因为只有一个质量for j in range(1, s+1):if dp[i - 1][j]:  # 找到前i-1个可以组合出质量jdp[i][j] = 1  # 不选第i个，前i个也可以组合出质量jdp[i][j + W[i]] = 1           # 用第i个数字，且做加法if j != W[i] :dp[i][abs(j - W[i])] = 1  # 用第i个数字，且做减法
print(sum(dp[-1]))  # dp[-1]就是dp的第一维的最后一个（即最后一行）

n = int (input ())
w = list (map(int,input ().split() ))
w.sort()    # 从小到大排序，可以减少计算时间
ans = set()  # 用set判重，用来存用多少种答案的
ans.add(w[0])
for i in w[1:]:for j in ans.copy ():     # ans.copy ()浅复制，不会因为该次循环而改变ansans.add(i)            # 只放新砝码i的质量ans.add(j + i)        # 将i和答案中每一个数放在同一侧：相加ans.add (abs(j - i))  # 将i和答案中每一个数放在不同测：相减
# 判断是否质量为0放在两层for循环之外，减少时间复杂度
if 0 in ans:                  # 质量为0的不考虑ans.remove(0)
print (len(ans))

n = int(input())
W = list(map(int, input().split()))
W.sort()  # 从小到大，减少时间复杂度
s = sum(W)  # 所有砝码之和（最大值）
si = [sum(W[0:i]) for i in range(1,n+1)]  # 质量W的前缀和
dp = [[0] * (s + 1) for _ in range(n)]
for i, w in enumerate(W):  # 初始化：前i个的砝码的质量为wdp[i][w] = 1
for i in range(1, n):  # 第0行不需要管，因为只有一个质量for j in range(1, si[i]+1):if dp[i - 1][j]:  # 找到前i-1个可以组合出质量jdp[i][j] = 1  # 不选第i个，前i个也可以组合出质量jdp[i][j + W[i]] = 1           # 用第i个数字，且做加法dp[i][abs(j - W[i])] = 1  # 用第i个数字，且做减法
print(sum(dp[-1][1:]))  # dp[-1]就是dp的第一维的最后一个（即最后一行）[1:]:不考虑质量为0的情况

n = int(input())
a = [list (map(int, input ().split())) for i in range (n)] # 用来读取每行个数不同的元素
#数组a[][]同时当成dp[][]用
for i in range(1, n):for j in range (0, i + 1):if j == 0: a[i][j] += a[i-1][j]        # 最左边元素elif j == i: a[i][j] += a[i-1][j-1]    # 最右边元素else:a[i][j] += max(a[i-1][j-1 : j+1]) # 中间（从上面左边/从上面右边）
if n & 1: print(a[-1][n//2])                          # 奇数行：在正中间
else:     print (max(a[-1][n//2-1], a[-1][n//2]))     # 偶数行：在正中间左边或者右边