题目来源:牛客题霸，动态规划专项https://www.nowcoder.com/activity/oj

零.引入

动态规划（Dynamic Programming，DP）是运筹学的一个分支，是求解决策过程最优化的过程。20世纪50年代初，美国数学家贝尔曼（R.Bellman）等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理，从而创立了动态规划。动态规划的应用极其广泛，包括工程技术、经济、工业生产、军事以及自动化控制等领域，并在背包问题、生产经营问题、资金管理问题、资源分配问题、最短路径问题和复杂系统可靠性问题等中取得了显著的效果 。

关于动态规划的基本概念

阶段:人为的将所求解的问题划分成若干个相互关联又相互独立的阶段，便问题的求解。问题不同，阶段也就不同；问题相同，阶段也有可能不同，但两种阶段都能够解决问题，殊途同归。

状态:将阶段映射到一个一维或多维的数组中，从而能够使我们的程序更好的进行统计

决策:要想在不同状态之间转移，需要进行决策。在思考决策时，应该保证将所有能够转移的方式都考虑到了。比方说，我想考虑状态有哪些决策，我就将所有能够到达状态的状态列举出来进行决策

无后效性:在转移的过程中，决策不能构成一个环，形式的说，就是如果状态能够间接或直接转移到状态，那么状态就一定不能间接或直接转移到状态(在某些期望DP中，可以使用高斯消元来实现后效性的转移。当然，在绝大多数的题目中都需要满足无后效性)

下面我以一道题来讲解这些基本概念在实际过程中的应用

NC1 连续子数组最大和(ACM版本)

本题中，我们将前个数看成一个阶段，那么我们可以将阶段映射到一个一维数组中

即就表示前个数中以结尾的最大子段和

如何转移？由于状态只能由状态转移过来

即当前可以接到后面，也可以重新开始

容易发现这是没有后效性的，答案即为中的最大值

一.线性DP

NC2 不相邻取数

设表示前个数中是否强制被选择所选出来的最大和

转移分两种

强制选

强制不选

NC3 nico和niconiconi

有了前两题的经验，设计状态应该不算难，同样设表示前个字符的最大价值

转移时讨论能否构成A,B,C

由于前缀和与差分和本文的动态规划无关，故略去

二.二维DP

NC9 字母收集

DP状态的设计有一个很重要的原则，就是无后效性

本题设表示从走到的最大收益

由于题目规定只能向下或右走，因此转移不会出现环的情况

转移其中表示这个点的字母的价值

NC10 小红取数

拿到题感觉很不可做，但看了看数据范围，笑了(，由于很小，这启发我们将其压到状态中

设表示在前个数中选若干个，使得这些数之和除以的余数的最大和，特别的，若无法得到则此时

转移不难

f[i][(j+a[i])%k]=max(f[i-1][j],f[i][(j+a[i])%k]+a[i])

三.背包

NC11 【模板】01背包

朴素DP,鉴于上一道题的经验，设表示前件物品中，体积恰为的最大收益

分别表示选不选这件物品，答案为

注意到当前的只能由转移过来，故可以把其压掉，同时由于不能将自己覆盖了，所以还需倒着进行更新

f[0]=1;
for(int i=1;i<=n;++i)
    for(int j=m;j>=v[i];--j)
        f[j]=max(f[j],f[j-v[i]]+w[i]);

NC12 【模板】完全背包

相较于上一道题，此题增加了相同物品重复选的性质

考虑上一题将第二维循环颠倒其实就是为了限制每个数只能选一次，因此对于本题直接正着来就行了

f[0]=1;
for(int i=1;i<=n;++i)
    for(int j=v[i];j<=m;++j)
        f[j]=max(f[j],f[j-v[i]]+w[i]);

四.区间dp

NC13 [CQOI2007]涂色PAINT

由于每次我可以从中间开始染色，因此之前从开始统计的DP就不可取了

设表示将区间染成合法的最小步数

注意到只有长度小的区间才会向长度大的区间产生贡献，因此该DP是没有后效性的

转移

其中前两个转移的复杂度为，后两个为，因此总复杂度为