DP也叫作动态规划相比进入到普转提的我们在它面前也只能甘拜下风感性来讲一位名人曾说过DP并不是枯燥无味的它只是一种将一个大问题拆成若干个小问题的艺术线性DP背包DP树形DP状态压缩DP数位DP一个个痛苦的回忆在我脑边回响没事今天我们将要从线性DP开始讲起~~线性DP任何一个伟大的思想都有一个微不足道的开始。。。学习动态规划之前我们先来纠正一下DP 的概念首先我们要明白贪心和动态规划是两种不同的思想。贪心在贪心中我们每一步都只保留最优解相当于是每个阶段只保留唯一的 状态贪心的问题中我们认为局部的最优一定能导向全局的最优。动态规划局部的最优并不意味着全局的最优每一种情况我们都要考虑到也就是说我们要保留当前阶段产生的任何一种状态由当前的最优解转化为全局的最优解。。。递推与DP在我看来两者并没有什么本质上的区别都是由之前的状态转化为当前的状态要真要为两者进行区分只能说递推往往没有决策的内容在每 一步都是用同样的选择来转移。而dp在每一阶段的转移中都需要根据情况 做出决策每一步选择的状态都是不同的。下面我们来学习一下DP的几大特征1.最优化原理如果问题的最优解所包含的子问题也是最优的就称该问题具有最优子结 构即满足最优化原理。2.无后效性即某阶段状态一旦确定就不受这个状态以后决策的影响。也就是说某 状态以后的过程不会影响以前的状态只与当前状态有关。3.有重叠子问题:即子问题之间是不独立的一个子问题在下一阶段决策中可能被多次使用到。DP的三要素阶段状态和决策在每一个题中如果能在保证不超时的情况下找到正确的这三要素那么大部分的DP对你来说就是小菜一碟如果遇到数位DP和状态压缩DP就当我没说线性DP在动态规划中是较为基础的下面我们来看一道题来辅助理解题目描述某国为了防御敌国的导弹袭击发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷虽然它的第一发炮弹能够到达任意的高度但是以后每一发炮弹都不能高于前一发的高度。某天雷达捕捉到敌国的导弹来袭由于该系统还在试用阶段所以只有一套系统因此有可能不能拦截所有的导弹。输入导弹的枚数和导弹依次飞来的高度雷达给出的高度数据是不大于30000的正整数每个数据之间有一个空格计算这套系统最多能拦截多少导弹输入格式第一行数字n表示n个导弹(n200)第二行n个数字表示n个导弹的高度输出格式一个整数表示最多能拦截的导弹数目这是一道线性DP的经典题目先假设本题我们用贪心来写每次如果当前导弹可以拦截那么我们就让最大拦截数1但考虑到当前的导弹发射顺序是无序的如果用贪心可能会死的很惨考虑不到最优解这时DP就派上了大用场我们枚举每一次导弹的发射状况并与前面的导弹进行比较如果当前导弹的高度小于前面那我们就让自身能拦截导弹的最大数目与当前枚举导弹的数目1进行比较作为DP基础题思维难度较为简单具体代码如下#includebits/stdc.h using namespace std; int n,a[10005],f[10005],ans0,sum0,p[10005]; int read(){ int x; scanf(%d,x); return x; } int h1(int x){ if(f[x]) return f[x]; f[x]1; for(int i1;ix;i){ if(a[i]a[x]){ f[x]max(f[x],f[i]1); } } return f[x]; } int main(){ nread(); for(int i1;in;i){ a[i]read(); } for(int i1;in;i){ ansmax(ans,h1(i)); } printf(%d\n,ans); }前缀和优化线性DP前缀和对于在座的各位大牛们想必也不陌生哈当遇到较为复杂的DP时通过前缀和记录当前阶段状态之和可以大幅度减少时间复杂度完成状态的递推。前缀和优化可能是除树状数组等其他非线性优化以外最重要的优化难度也相对较高下面我们就来引入一个例题来浅分析一二。题目描述有 N 个编号为 1,2,⋯ ,N 的孩子他们要分享K个糖果。对于每个孩子必须得到 0 到之间数目的糖果含 00和。同样分完之后不能有糖果剩下。找出他们分享糖果的方法数对取模的结果。在两种分糖果方法中存在一个孩子得到不同数量的糖果时这两种方法被认为是不同的。输入格式第一行两个由空格隔开的数字N 和K。接下来一行,N 个空格隔开的数 a1​ 到aN​ 。N K输出格式找出孩子们分享糖果的方法数对取模的结果。表示前i个人分了就个糖果的方案数,枚举k表示i号孩子拿到了几个糖果前i-1个人要分j-k个糖果所以我们第一层可以枚举前i个孩子的编号枚举总糖果数从0~k,同时 我们还要枚举这一个孩子的可以拥有的糖果数。总复杂度为,具体代码如下#includebits/stdc.h using namespace std; typedef long long ll; const int N1e510,mod1e97; ll n,K,dp[105][N],sum[105][N]; int a[N]; int main() { scanf(%lld%lld,n,K); for(int i1;in;i){ scanf(%d,a[i]); } dp[0][0]1,sum[0][0]1; for(int i1;in;i){ for(int j0;jK;j){ for(int k0;kmin(a[i],j);k){ dp[i][j](dp[i][j]dp[i-1][j-k])%mod; // printf(sgsdf); } } } printf(%d,dp[n][K]); }但是考虑n 的范围发现会超时我们可使用前缀和优化设则有∴ 我们就可以省去一重循环减少了对枚举i个孩子糖果数量k的枚举具体代码如下#includebits/stdc.h using namespace std; typedef long long ll; const int N1e510,Mod1e97; ll n,K,dp[105][N],sum[105][N]; int a[N]; int main() { scanf(%lld%lld,n,K); for(int i1;in;i){ scanf(%d,a[i]); } dp[0][0]1,sum[0][0]1; for(int i1;in;i){ sum[i][0]1; for(int j1;jK;j) (sum[i-1][j](sum[i-1][j-1]dp[i-1][j])%Mod)%Mod; for(int j0;jK;j){ if(j-min(a[i],j)) dp[i][j](sum[i-1][j]-sum[i-1][j-min(a[i],j)-1])%Mod; else dp[i][j]sum[i-1][j]; } // k:0~min(a[i],j) // for(int k0;kmin(a[i],j);k){ // dp[i][j](dp[i][j]dp[i-1][j-k])%mod; // } } printf(%lld,(dp[n][K]Mod)%Mod); }前缀和优化总结写关于DP优化的题目一定要先写一个符合DP基本思路的超时但正确的代码在此基础上查找可能优化的那重循环的枚举范围再通过计算出前缀和的公式来优化层层推进一个AC的代码才可以出世。总结本次学习的线性DP和前缀和优化在DP这个大家族中较为简单但题目稍难还需读者自行理解后在面对题目我的一位友人曾说过动态规划就像人生在当前阶段你所做的策略未必是最优的但真正的答案只会在n次的非最优转化到最后的成功来吧看谁能笑到最后本次博客的公式部分由同机房友人魏诗辰制作特别鸣谢