dp算法部分是个人感受上了几次课做了几个问题后，觉得这个dp和以前的算法不一样，是思想，更偏向于问题的分析。 另一方面，代码只是表示问题解决的过程，并没有制造太多问题，但老实说，有时完全没有考虑如何进行状态变换。 看问题也需要一点时间，但是需要思考的首先，从简单的事情开始，其实有最基本的模板类型。 例如，最大上升子串、最大公共子串等。 一些问题的根本思想就是这个。 但是，数据的处理很麻烦。 例如，我们必须继续了解某个问题是数据输出的顺序号，为什么这样做，我们不知道。 继续想，我觉得最好多用手写。 有助于理解。
这样的问题具体解决的时候，有一点是共通的。 例如，dp[i]表示前I个数据怎么样了，从这个具体的展开开始进行所谓的状态变化
具体来说，列举几个自己掌握的模板的例子吧
1.最大上升子序列问题
分析：要寻找最大的，找到以dp[i]结尾的上升序列，然后取最大值即可
int main () { int n，sum； for(intI=1； i=n； I ) dp[i]=1； for(intj=2； ji； j ) if(a(j ) a (I ) ) DP ) I )=max ) DP ) I，DP ) j )1)； coutdp[i]endl；2.最大公共子序列
思想： dp[i][j]表示a的最初I个和b的最初j个是相同的个数
过渡方程： if(a(I )==b ) j ) (DP ) I ) ) j )=DP(I-1 ) ) j-1 ) 1；
else dp[i][j]=max(dp[i][j-1]，dp[i-1][j] )
3.最大字段和
思想： dp[i]表示前I个数据的字段和
# includeiostreamusingnamespacestd； int main () ) { int dp[100]； int sum=-1； inta [6]={ 5，6，- 1，5，4，-7}； for(intI=0； i=5； I ) DP[I]=max(DP[I-1]a[I]，0 )； if(DP[I]sum ) sum=dp[i]； } coutsumendl； 返回0； } 注意一个问题 字段是连续的 序列可以不连续！
最后一个例子
大脑关于路径输出的痛苦，只有写下来才能知道。 真是不可思议的操作。 这个代码不是自己写的。 解决了检索的问题，明白了。 必须掌握这个方法
# include iostream # includealgorithmusingnamespacestd； struct node{int w； int s； int no； }mice[1005]； struct node2{int sum=1； int pre=0； }dp[1005]； BOLCMP(nodea，node b ) if ) a.w==b.w ) return a.s b.s； return a.w b.w； (}int main ) ) {int k=0，max，t； while (CIN mice [ k ].wmice [ k ].smice [ k ].wmice [ k ].s ) {mice[k].no=k 1； k； }sort(mice，mice k，cmp )； max=1； t=1； for(intI=1； i k； I ) for(intj=0； j i； j () if ) mice [ j ].smice [ I ].smice [ j ].wmice [ I ].w ) /质量大速度小) if(DP[I].sumDP[j].sum1) /最大值}}if(DP[I].summax ) {max=dp[i].sum； t=i； }}cout max endl； int m[1005]； for(intI=1； i=max； I ) m(I )=t； t=dp[t].pre； }for(intj=max； j=1； j--coutmice[m[j]].noendl； }关键是路径输出很难分辨(对我来说) ) )。
{if(DP[I].sumDP[j].sum1) /最大连续序列{dp[i].sum=dp[j].sum 1； dp[i].pre=j； //用于记录的数据的编号}}if(DP[I].summax ) {max=dp[i].sum； t=i； //这是最后的序列号}}cout max endl； int m[1005]； for(intI=1； i=max； I ) m(I )=t； t=dp[t].pre； //我不知道具体为什么这么操作，试了一下确实如此。 }for(intj=max； j=1； j--coutmice[m[j]].noendl； }