花了许多天时间，写了大概10来道题，有几道简单，和两个作用属于提高+的吧。简单题没什么好说的，主要就是板子。从中等题开始，要么是对dp进行了优化，要么就是和其他的算法进行了结合，算是灵活性更高了。到了难的题目（对我来说），需要结合比较多数学知识，去自己手玩一下，去试和尝试证明一些方法再去进行DP，这里难的对我来说就是首先找到进行dp的状态是什么，然后用数学知识去进行一些推导，对于这种题目我觉得需要去多练习逐渐提升自己的数学思维，并且可以不用只练关于dp的，很多其他类型的也能做到锻炼数学思维。后面有机会写一篇关于数学思维题目的总结。这里抱歉很多题解都没写全，因为实在有些耗时，太杂了，我后面尽量写题的时候就把思路列好，后面写题解就方便点，还好这些题洛谷上都有，各位可以自行查看，这篇博客也主要是自己做一个总结还有挑一些题目尽量让各位多看几种，不要一直做重复的，当然练习的时候重复还是很重要的。
总结
先分享一下做了些DP题后的思考。首先见识各种模型还是很重要，让我们能很快找到去处理一些子问题的方法。其次就是要理清怎么去解决这类题目，首先dp其实就是把一个问题分解成若干个子问题，对于每一个子问题得到最优解来得到问题的最优解。我来总结一下我做这些题的思考方向：
·第一步是子问题是什么，因为我们要通过对子问题的最优决策来得到问题的最优解
·第二步是找到状态，这一步在我的观点上是区分DP题的难度的一个点，有时候很难一下就找到，要多次尝试和思考
·第三步是去寻找状态转移方程，我们已经确定状态后很自然就去推导状态转移方程
·第四步是确定各种边界条件
·最后一步是想是否需要优化和如何优化
还有一个点就是我们要怎么确定这道题是否要用DP，因为我做的时候我是直接标签去找线性DP的题的，所以我很清楚就是要用DP解决，但是我们打比赛或做一些题的时候不可能有tag告诉我们是什么类型，所以我们要明白如何去判断是否使用DP。这里分享一下阅读一些大佬的文章和自己一些了解后做的总结：
·是否有重叠子问题。比如在在解决问题时候子问题被重复计算，这种我们通常会使用记忆化来解决
·是否有最优子结构。就是这个问题是否能够由最优子结构构造出来
·决策无后效性。就是我们的决策只会改变当前和未来的状态，与过去无关
但是实际上最好的学习方法就是自己去选择题目去做并定期总结，接下来就展示几个各个难度的题
简单
P12833 [蓝桥杯 2025 国 B] 斐波那契字符串
题目描述
斐波那契字符串 $S$ 是由 $\tt 0$ 和 $\tt 1$ 所组成的字符串，其生成规则如下：
- $S_1 = \tt 0$。
- $S_2 = \tt 1$。
- 对于任意正整数 $n (n \geq 3)$，$S_n = S_{n-2} + S_{n-1}$（“+”表示字符串拼接）。
例如：$S_3 = 01$、$S_4 = 101$、$S_5 = 01101$。
在斐波那契字符串 $S$ 中，定义逆序对为满足以下条件的整数对 $(i, j)$:
- $1 \leq i < j \leq |S|$（其中 $|S|$ 表示 $S$ 的长度）。
- $S[i] = 1$（第 $i$ 个字符为 $\tt 1$）并且 $S[j] = 0$（第 $j$ 个字符为 $\tt 0$）。
现在，给定一个正整数 $N$，请你计算出 $S_N$ 中所有逆序对 $(i, j)$ 的总数。由于结果可能很大，请输出其对 $10^9 + 7$ 取余后的值。
输入格式
输入的第一行包含一个整数 $T$，表示测试用例的数量。
接下来的 $T$ 行，每行包含一个整数 $N$，表示要计算的斐波那契字符串的序号。
输出格式
对于每个测试用例，输出一行，包含一个整数，表示 $S_N$ 中所有逆序对的总数对 $10^9 + 7$ 取余后的结果。
输入输出样例 #1
输入 #1
|
|
输出 #1
|
|
说明/提示
【样例说明】
对于 $N = 3$，$S_3 = 01$，逆序对总数为 0。
对于 $N = 5$，$S_5 = 01101$，逆序对为 $(2, 4)$、$(3, 4)$，总数为 2。
【评测用例规模与约定】
对于 20% 的评测用例，$1 \leq T \leq 20$，$3 \leq N \leq 35$。
对于 100% 的评测用例，$1 \leq T \leq 10^5$，$3 \leq N \leq 10^5$。
思路
我们那这道题来印证上面提到的思考方式。首先这道题存在子问题，并且可以由最优决策的子问题来解决问题，所以我们基本可以判断他是DP。
我们先来确定子问题，这题很明显，就是上两个字符串。
接下来确定状态，也不难看出状态就是逆序对数。
接下来推导状态转移方程，对于S_i = S_i-2 + S_i-1,S_i-2的逆序对不会变，而S_i-1的1与S_i-2的0组合会新增逆序对，那么我们的方程就很容易推导出来了：
f[i] = f[i-2] + f[i-1] + one[i-1]*zero[i-2]
这道题的边界也很清晰，毕竟这是一个简单题，到此问题解决。
这里就不展示代码了，各位自己思考尝试一下。
中等
P1020 [NOIP 1999 提高组] 导弹拦截
题目描述
某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。
输入导弹依次飞来的高度，计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
输入格式
一行，若干个整数，中间由空格隔开。
输出格式
两行，每行一个整数，第一个数字表示这套系统最多能拦截多少导弹，第二个数字表示如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
输入输出样例 #1
输入 #1
|
|
输出 #1
|
|
说明/提示
对于前 $50%$ 数据（NOIP 原题数据），满足导弹的个数不超过 $10^4$ 个。该部分数据总分共 $100$ 分。可使用 $\mathcal O(n^2)$ 做法通过。
对于后 $50%$ 的数据，满足导弹的个数不超过 $10^5$ 个。该部分数据总分也为 $100$ 分。请使用 $\mathcal O(n\log n)$ 做法通过。
对于全部数据，满足导弹的高度为正整数，且不超过 $5\times 10^4$。
此外本题开启 spj，每点两问，按问给分。
NOIP1999 提高组 第一题
$\text{upd 2022.8.24}$：新增加一组 Hack 数据。
思路
这道题的思路也比较清晰，这里就不像前一个一步步走了，讲一下大致的思路。我们要寻找一个最长非递增子序列，我们假设最长的结束在索引i，我们遍历前面j < i， 然后更新dp[i] = max(i, {dp[j]+1})。
但是这道题要我们在O(nlogn)解决，说明这样单纯搞是不行的。看到logn我的第一个想法就是二分，结果确实可行。我们想要找到最大的dp[j],那么我们就假设dp[j] = x,令f[x]为长度为x的序列最大的最后一个数的大小，我们可以通过反证法去证明f[x]是一个单调不增的,由dp[j] <= f[x], dp[j] >= dp[i],得到dp[i] <= f[x]。因此我们要找到尽可能大的 x 满足 h(i)≤f[x]。考虑二分。
接下来就是考虑第二问，这里用到了Dilworth’s theorem, 在之前的博客提到过，有兴趣可以去了解下。
P1018 [NOIP 2000 提高组] 乘积最大
题目背景
NOIP2000 提高组 T2
题目描述
今年是国际数学联盟确定的“2000——世界数学年”，又恰逢我国著名数学家华罗庚先生诞辰 90 周年。在华罗庚先生的家乡江苏金坛，组织了一场别开生面的数学智力竞赛的活动，你的一个好朋友 XZ 也有幸得以参加。活动中，主持人给所有参加活动的选手出了这样一道题目：
设有一个长度为 $N$ 的数字串，要求选手使用 $K$ 个乘号将它分成 $K+1$ 个部分，找出一种分法，使得这 $K+1$ 个部分的乘积能够为最大。
同时，为了帮助选手能够正确理解题意，主持人还举了如下的一个例子：
有一个数字串：$312$，当 $N=3,K=1$ 时会有以下两种分法：
- $3 \times 12=36$
- $31 \times 2=62$
这时，符合题目要求的结果是：$31 \times 2 = 62$。
现在，请你帮助你的好朋友 XZ 设计一个程序，求得正确的答案。
输入格式
程序的输入共有两行：
第一行共有 $2$ 个自然数 $N,K$。
第二行是一个长度为 $N$ 的数字串。
输出格式
结果显示在屏幕上，相对于输入，应输出所求得的最大乘积（一个自然数）。
输入输出样例 #1
输入 #1
|
|
输出 #1
|
|
说明/提示
数据范围与约定
对于 $60%$ 的测试数据满足 $6≤N≤20$。
对于所有测试数据，$6≤N≤40,1≤K≤6$。
思路
这道题大家可以自己思考试试，比较简单，就是加了个高精度，状态和方程都比较好想。
P13871 [蓝桥杯 2024 省 Java/Python A] 吊坠
题目描述
小蓝想制作一个吊坠，他手上有 $n$ 个长度为 $m$ 的首尾相连的环形字符串 ${s_1, s_2, \cdots, s_n}$，他想用 $n-1$ 条边将这 $n$ 个字符串连接起来做成吊坠，要求所有的字符串连完后形成一个整体。连接两个字符串 $s_i, s_j$ 的边的边权为这两个字符串的最长公共子串的长度（可以按环形旋转改变起始位置，但不能翻转），小蓝希望连完后的这 $n-1$ 条边的边权和最大，这样的吊坠他觉得最好看，请计算最大的边权和是多少。
输入格式
输入的第一行包含两个正整数 $n, m$，用一个空格分隔。
接下来 $n$ 行，每行包含一个长度为 $m$ 的字符串，分别表示 $s_1, s_2, \cdots, s_n$。
输出格式
输出一行包含一个整数表示答案。
输入输出样例 #1
输入 #1
|
|
输出 #1
|
|
说明/提示
【样例说明】
连接 $\langle 1,2\rangle, \langle 2,3\rangle, \langle 2,4\rangle$，边权和为 $4 + 2 + 2 = 8$
【评测用例规模与约定】
对于 $20%$ 的评测用例，$1 \leq n, m \leq 10$；
对于所有评测用例，$1 \leq n \leq 200$，$1 \leq m \leq 50$。所有字符串由小写英文字母组成。
思路
这道题也是不难，主要就是给大家展示DP与其他算法的结合，这个加入的最大生成树，各位也可以练手
P5124 [USACO18DEC] Teamwork G
题目描述
在 Farmer John 最喜欢的节日里，他想要给他的朋友们赠送一些礼物。由于他并不擅长包装礼物，他想要获得他的奶牛们的帮助。你可能能够想到，奶牛们本身也不是很擅长包装礼物，而 Farmer John 即将得到这一教训。
Farmer John 的 $N$ 头奶牛（$1\le N\le 10^4$）排成一行，方便起见依次编号为 $1\dots N$。奶牛 $i$ 的包装礼物的技能水平为 $s_i$。她们的技能水平可能参差不齐，所以 FJ 决定把她的奶牛们分成小组。每一组可以包含任意不超过 $K$ 头的连续的奶牛（$1\le K\le 10^3$），并且一头奶牛不能属于多于一个小组。由于奶牛们会互相学习，这一组中每一头奶牛的技能水平会变成这一组中水平最高的奶牛的技能水平。
请帮助 FJ 求出，在他合理地安排分组的情况下，可以达到的技能水平之和的最大值。
输入格式
输入的第一行包含 $N$ 和 $K$。以下 $N$ 行按照 $N$ 头奶牛的排列顺序依次给出她们的技能水平。技能水平是一个不超过 $10^5$ 的正整数。
输出格式
输出 FJ 通过将连续的奶牛进行分组可以达到的最大技能水平和。
输入输出样例 #1
输入 #1
|
|
输出 #1
|
|
说明/提示
在这个例子中，最优的方案是将前三头奶牛和后三头奶牛分别分为一组，中间的奶牛单独成为一组（注意一组的奶牛数量可以小于 $K$）。这样能够有效地将 $7$ 头奶牛的技能水平提高至 $15$、$15$、$15$、$9$、$10$、$10$、$10$，和为 $84$。
思路
这道题的状态状态和状态转移方程算更难想一点的，多了一个考虑几个成一组的状态，也是一个我感觉比较好的中等题吧，虽然挺多大佬说是简单题，好想的DP，但是我没看过的就是好题嘛。
结语
我们写了难的题但是没放上来，主要是我没能做到很好的理解透所以没办法去进行挑选和讲解，如果一股脑全加上来，各位自己去搜可以搜到更多的，所以这个留到以后我能去理解和有能力很好的解决后来补充。