DP分析：1.状态表示 2.状态计算

状态表示分为：集合和属性
对于集合，第一维就是第i个物品，后面几个维度都是限制

状态计算：对应集合的划分
一般就是找最后一个不同点作为划分的依据，这里就是第i个物品是否选择
划分要做到：1.不重复 2.不遗漏

背包问题

//如何优化: j从大到小，j>=v[i], i的维度可以删去，我们只需保存上一场层的)
01背包问题(模板)： https://www.acwing.com/file_system/file/content/whole/index/content/11595950/

//如何优化: 列出f(i,j) 和 f(i,j - v), f(i,j - v)再加上w, 看有什么相同的部分，然后合并
完全背包问题(模板)： https://www.acwing.com/solution/content/237290/

//对于选法，基本都是背包问题。对于题目而言 先不考虑优化，最后考虑优化

货品系统(完全背包问题模板): https://www.acwing.com/solution/content/237373/

//裴蜀定理: ax + by = m 有解当且仅当m是d(a和b的最大公约数)的倍数。
//int d = 0; 开始先设d为0，然后gcd(0,x) = x 方便计算
包子凑数： https://www.acwing.com/solution/content/237309/

砝码称重: https://www.acwing.com/solution/content/237461/

倍数问题： https://www.acwing.com/solution/content/240835/

数组分割： https://www.acwing.com/blog/content/52576/

蜗牛： https://www.acwing.com/activity/content/code/content/7585145/

线性DP

//求数值严格单调递增的子序列的长度最长是多少
最长上升子序列(模板): https://www.acwing.com/solution/content/237024/
//是A的子序列又是B的子序列的字符串长度最长是多少
最长公共子序列(模板): https://www.acwing.com/solution/content/237037/

乌龟棋: https://www.acwing.com/file_system/file/content/whole/index/content/11589401/
接龙数列(最长上升子序列模板): https://www.acwing.com/solution/content/240265/
松散数列(线性DP或者状态DP)： https://www.acwing.com/solution/content/237140/

区间DP

区间DP：
1.先枚举区间长度
2.再枚举左端点(左端点条件：左端点+length - 1 < n )
3.右端点 = 左端点+length-1)

//前缀和+区间DP
石子合并(模板): https://www.acwing.com/solution/content/238097/

密码脱落: https://www.acwing.com/solution/content/238111/

//博弈论 看看思想
游戏(博弈论): https://www.acwing.com/file_system/file/content/whole/index/content/11641147/

单调队列

//最好从1开始存放和枚举
//找左边第一个比自己小的数 从1 到 n 枚举 tt !=0&&st[tt] >= a[i] tt–
//找右边第一个比自己大的数 从n 到 1 枚举 tt !=0&&st[tt] <= a[i] tt–
//如果 tt > 0 说明栈顶元素就是答案 res = st[tt] 最后放入元素 st[++tt] = a[i]
单调栈(模板)： https://www.acwing.com/solution/content/235737/

直方图中最大的矩形(单调栈)： https://www.acwing.com/solution/content/236523/

//可以用二维前缀和直接暴力做
矩形牛棚(直方图中最大的矩形)： https://www.acwing.com/solution/content/236574/

滑动窗口(模板)： https://www.acwing.com/solution/content/235756/

子矩阵(滑动窗口)： https://www.acwing.com/solution/content/236637/

贪心

区间选点： https://www.acwing.com/solution/content/241307/
耍杂技的牛： https://www.acwing.com/solution/content/241317/

填充： https://www.acwing.com/solution/content/241326/
三国游戏： https://www.acwing.com/solution/content/241337/
平均： https://www.acwing.com/solution/content/241382/
买二赠一： https://www.acwing.com/solution/content/241411/

数学

矩形面积： https://www.acwing.com/blog/content/52588/

进制转化： 原文链接： https://blog.csdn.net/qq_52108058/article/details/129363978
算log: https://www.acwing.com/blog/content/52290/