---恢复内容开始---
三道题，第一道就比较简单，从上到下或者从下到上都可以
递归方程：dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+a[i][j];
1 #include<iostream> 2 using namespace std; 3 int a[110][110],dp[110][110]; 4 int n; 5 int main() 6 { 7 cin>>n; 8 for(int i=1;i<=n;i++){ 9 for(int j=1;j<=i;j++){ 10 cin>>a[i][j]; 11 } 12 } 13 int maxx=-1; 14 for(int i=1;i<=n;i++){ 15 for(int j=1;j<=i;j++){ 16 dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+a[i][j]; 17 maxx=max(maxx,dp[i][j]); 18 } 19 } 20 cout<<maxx; 21 return 0; 22 }
第二题
递归方程：dp[i]=max(dp[i-1]+a[i],a[i]);
dp【i】表示已第i个位置为结束的最大字段和，要不是自己，要不就是加上前一个，维护一下最大值就好
代码：
#include<iostream> using namespace std; int n; int a[10010],dp[10010]; int main() { cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; int maxx=-1; for(int i=1;i<=n;i++){ dp[i]=max(dp[i-1]+a[i],a[i]); maxx=max(maxx,dp[i]); } if(maxx<0) maxx=0; cout<<maxx; }
得初始化，i j一个为0的时候 dp【i】【j】就等于另一个，这种情况可理解为全删掉或者全增加。
第三题
递归方程：
#include<iostream> #include<string.h> using namespace std; char s[2010],t[2010]; int dp[2010][2010]; int main() { cin>>s+1>>t+1; int len1=strlen(s+1),len2=strlen(t+1); //cout<<len1<<" "<<len2<<endl; if(s[1]==t[1]) dp[1][1]=0; else dp[1][1]=1; for(int j=0;j<=len2;j++) dp[0][j]=j; for(int i=0;i<=len1;i++) dp[i][0]=i; for(int i=1;i<=len1;i++){ for(int j=1;j<=len2;j++){ if(s[i]!=t[j]) dp[i][j]=min( dp[i-1][j-1], min(dp[i][j-1] , dp[i-1][j] ) )+1; else dp[i][j]=dp[i-1][j-1]; } } cout<<dp[len1][len2]; }
---恢复内容结束---
原文：https://www.cnblogs.com/qq2210446939/p/11716809.html
