1.动态规划基础
(1)线性DP
1）什么是DP（动态规划）
DP（动态规划）全称Dynamic Programming，是运筹学的一个分支，是一种将复杂问题分解成很多重叠的子问题，并通过子问题的解得到整个问题的解的算法。
在动态规划中有一些概念：
状态：就是形如dp[i] [j] = val的取值，其中i，j为下标，也是用于描述、确定状态所需的变量，val为状态值。
状态转移：状态与状态之间的转移关系，一般可以表示为一个数学表达式，转移方向决定了迭代或递归方向。
最终状态：也就是题目所求的状态，最后的答案。
2）动态规划的分析步骤
①确定状态，一般为“到第i个为止，xx为j（xx为k）的方案数/最小代价/最大价值”，可以根据数据范围和复杂度来推理。
②确定状态转移方程，即从已知状态得到新状态的方法，并确保按照这个方向一定可以正确地得到最终状态。根据状态转移的方向来决定使用迭代法还是递归法、记忆化。
③确定最终状态并输出。
(2)二维DP
二维DP就是指DP数组的维度为二维的DP（当然有时候可能会三维四维，或者存在一些优化使得它降维成一维），广义的来讲就是有多个维度的DP，即用于描述DP状态的变量不止一个。
(3)最长上升子序列LIS
LIS（最长上升子序列）是一个经典的DP模型。
子序列指的是一个序列中，按照原顺序选出若干个不一定连续的元素所组成的序列。在求解LIS时，一般我们会设dp[i]表示1~i序列中以a[i]结尾的最长上升子序列的长度，状态转移方程为：
dp[i] = max(dp[i] + 1), if a[i] > a[j]
表示a[i]要插入到不同子序列后面的情况。
(4)最长公共子序列LCS
LCS（Longest Common Subsequence最长公共子序列）是一个经典的DP模型。
LCS问题是给定两个子序列A和B，求它们的最长公共子序列。
在求解LCS时，一般我们会设dp[i] [j]表示A[1 ~ i]序列和B[1 ~ j]序列中（不规定结尾）的最长公共子序列的长度，状态转移方程为：
if a[i] = b[j] : dp[i] [j] = dp[i -1] [j - 1] + 1
else dp[i] [j] = max(dp[i - 1] [j], dp[i] [j - 1])
当a[i] = b[j]时，可以将他们作为插入到LCS的后面，使得长度变长1，当a[i] != b[j]时，说明此时LCS不会延长，那就要从dp[i - 1] [j]和dp[i] [j - 1]中取大的作为最长的长度。
标签：状态,LCS,杯备赛,笔记,蓝桥,dp,序列,最长,DP From： https://blog.csdn.net/weixin_71201865/article/details/145247688