适合萌新的DP训练题单（大概？）

概述

因为本蒟蒻不咋会DP推导，或者老是在错误的方向越走越远，所以开一篇博客来专门存DP推导的一些练习。当个题单吧，顺便方便记忆，规避错误

打*的为还没写博客或者还不会的

很多题目是acwing活动里的如果找不到的话可以去别的OJ里搜一样的题目

正文

题单

线性DP

类型	题目	链接	特点	载体	注意点
LIS模型	怪盗基德的滑翔翼	LIS模型【提高课】	任选一个点一个方向，左右取max	子序列
LIS模型	登山	同上	山峰型，左右相加	子序列
LIS模型	合唱队形	同上	左右相加，子序列概念	子序列
LIS模型	友好城市	同上	排序，自变量与因变量的抽象，二元组	子序列，二元组	二元组排序思想
LIS模型	最大上升子序列和	同上	最大长度变为最大和	子序列
LIS模型	拦截导弹	同上	贪心，最小覆盖链定理	子序列	证明方式
LIS模型	导弹防御系统	同上	DFS+最小覆盖链	子序列
LIS模型/LCS模型	最长公共上升子序列	同上	LIS和LCS	子序列，字符串
LCS模型	最短编辑距离 *	变为相同，最少操作次数	字符串，操作	想清楚操作前后，是怎么转移的
数字三角形模型	摘花生	数字三角形模型【提高课】	三角形转矩形	二维数组，路径
数字三角形模型	最低通行费	同上	步数转为不走回头路	二维数组,路径
数字三角形模型	方格取数	同上	走两次，走过的变为0	二维数组，路径	同时走
数字三角形模型	传纸条	同上	双向传，传过的不能再传	二维数组，路径	对无法转移状态的特殊处理
普通线性DP	乌龟棋	【线性DP】乌龟棋	限制操作次数	一维数组，操作	转移的时候要注意操作是否存在

背包

以选法为载体

状压DP

区间DP

树形DP

数位DP

以整数为载体

题目	链接	特点注意点
A｜B *	牛客小白月赛31A	位运算
有趣的数

更抽象，更普适的DP扩展，以及常见DP类型思考方式

序列类型DP

LIS可以扩展为序列类型DP，以序列为载体，序列元素间往往有某种关系

路径类型DP

数字三角形可以扩展为路径类型DP

组合类型DP

背包可以扩展为组合类型DP，只和怎么选有关，以选法为载体