背包
1.字串和子序列
子序列:不连续的
字串 :连续的
2.DP记忆化搜索
方法——结尾法
1. dp[i] 表示以下标 i 作为结尾的答案,ans是{dp[1]~dp[n]}的最优值
2. 记录长度?dp[i]——Answer: dp[i] 表示 以 a[i] 作为结尾的最长上升子序列\textbf{记录长度?}dp[i] ——Answer:\large{ \textbf {\color{red} dp[i] 表示 以 a[i] 作为结尾的最长上升子序列}}记录长度?dp[i]——Answer: dp[i] 表示 以 a[i] 作为结尾的最长上升子序列
过程
1.1.1. $\large\textbf{遍历1 (i−1)1~(i-1)1 (i−1),用 j 下标表示}$
if(a[i]>a[j])if(a[i]>a[j])if(a[i]>a[j])转移条件
$dp[i]=max(dp[i],dp[j]+1); $
多维技巧
若低维状态无法描述问题,那我们开高维
dp[i][j]//什么含义
前缀法 定义状态
含义例子:dp[i]dp[i]dp[i]就表示111~iii处理完毕的结果,ans=dp[n]ans=dp[n]ans=dp[n].
dp[i][j]dp[i][j]dp[i][j]表示xxx序列处理完 前iii项,
YYY序列 处理完前j项的最大公共子序列
例题——LIS最长上升子序列\TEXTBF{例题}——LIS\TEXTBF{最长上升子序列}例题——LIS最长上升子序列
正解:
DAG模型
有向无环图 −>dp-> dp−>dp