我写这个博客是总结了这几天写的DP (渐进)问题的想法，以后不要忘记。 毕竟现在还很混乱。
阿数塔
题意)给一个数塔的话，只能从根节点忘记左右的儿子。 怎么去底边的话通过的数量之和最大？
想法：
变量宣言： dp[i][j]从以第I层的第j个节点为根节点的树中得到的最大和a[i][j] :保存主题给出的数塔
状态转移方程： dp[i][j]=根节点的值max (左部分树、右部分树) ) ) ) )。
核心代码：
for(intj=1； j=n； j ) maxsum[n][j]=a[n][j]； for(intI=n-1； i0； i-- ) for(intj=1； j=i； j ) max sum [ I ] [ j ]=max (max sum [ i1 ] [ j ] a [ I ] [ j ]，a[i][j] maxsum[i 1][j 1]； b小蜜蜂
题意)展示了蜜蜂蜂箱的形象，并做了编号。 蜜蜂只能通过六角形蜂箱右侧的三条边爬上旁边的蜂箱，询问蜜蜂从a房间到b房间可能的路线数量。
想法：从给定的图中可以得到规律：
1、a和b相差1，即b在a的右上或右下时，路线只有一种
2、a和b不同2时，即b紧挨a右边时，路线有2种。 例如，有1----3:1----2---3、1---- 3两种路线。
3、其他情况有递归公式。 a[i][i r]=a[i][i r-1] a[i][i r-2]，例如从到5的路线数=3的路线数到4的路线数。
核心代码：
for(intr=1； r=48； r ) for(intI=1； i r50； I ) if(r==1) a (I ) ) Ir )=1； ELSEif(r==2) a[i][i r]=2； elsea [ I ] [ IR ]=a [ I ] [ IR-1 ] a [ I ] [ IR-2 ]； }c-多段线分割平面
题意) )中文题目)需要的是用n条折线分割平面的最大数) )。
想法：观察一下就会发现，在相邻的两条线段(或放射线)上选择两点，连接这两点，原来的一个区域就会多分割一个。 因此，每次所有交点之间的区域数的增加量为[交点数-1]，但交点数的增加量是多少？ 因为是折线，所以在这里可以近似地认为是两条直线。 下面的“一条直线和n条直线可以有几个交点？ '因为答案必然是n个，所以在一条折线中为2*n (这里的n表示n条直线，所以在原题的情况下，1条折线和n条折线的交点数为2*(2*n ) ) )，所以第n条折线全部为与其他线相交，必然在其两端形成一条放射线，这两条放射线也可以分割区域，因此分割的增加量除了前面交点的增加量之外，还有这两条放射线的增加量这两张。
因此，f(n )=f ) n-1 ) ) (n-1 )-1 ) 2、化简f(n )=(n-1 )4 * n - 3；
这一节是从另一个博客上剪下的，详情请参阅地址：传送门)
核心代码：
cin m； cout 2*m*m - m 1 endl； Attack on Titans
题意：要求给出三种字符G R P，组成长度为n的字符串，有多少种这样的字符串需要满足两个条件(至少m个连续g，最多k个连续r )。
思路：首先主题提出了两个限制条件，一个多，一个少，很难解，至少考虑转换成多问题。
(至少连续m个g )=(最多n个g )-(最大连续M-1个g ) ) ) )。
统一以后，用渐进的思想来解决。 求解至多u个g、至多v个r时，长度为n的字符串有几种？
DP [ I ] [ 0，1，2 ] (如果第I个字符不包括第0个、第1个和第2个字符，则0表示g，1表示r，2表示p ) ) ) ) ) ) ) ) ) ) )。
因此，summ=DP [ I-1 ] [0] DP [ I-1 ] [1] DP [ I-1 ] [2]；
第I个字符为p时： dp[i][2]=summ；
第I个字符为g时： i=u时dp[i][0]=summ；
i==u 1 dp[i][0]=summ-1； (如果前u个字符全部为g，则减去) ) ) ) )。
iu1dp [ I ] [0]=summ-DP [ I-u-1 ] [1]-DP [ I-u-1 ] [2]； (前面有连续u字符时减少) ) ) ) ) )。
第I个字符为r时： i=v时dp[i][1]=summ； //同上
i==v 1 dp[i][1]=summ-1；
iv1dp [ I ] [1]=summ-DP [ I-v-1 ] [1]-DP [ I-v-1 ] [2]；
因此，核心代码如下
long long Cal () { dp[0][0]=1； dp[0][1]=0； dp[0][2]=0； for(intI=1； i=n； I ) )长整型和=(DP [ I-1 ] [0] DP [ I-1 ] [1] DP [ I-1 ] [2] ) %M； dp[i][2]=sum； if(I=u ) dp[i][0]=sum； elseif(I==u1 ) DP[I][0]=(sum-1 ) %M； else DP [ I ] [0]=(sum-DP [ I-u-1 ] [1]-DP [ I-u-1 ] [2] ) %M； if(I=v ) dp[i][1]=sum； elseif(I==v1 ) DP[I][1]=(sum-1 ) %M； else DP [ I ] [1]=(sum-DP [ I-v-1 ] [0]-DP [ I-v-1 ] [2] ) %M； }返回(DP [ n ] [0] DP [ n ] [1] DP [ n ] [2] ) %M； } emmmm在持续更新的情况下，在DP这一漫长的道路上缓慢行驶。