非常简单的动态规划

#include<bits/stdc++.h>
using namespace std;
int main()
{
  int n,i,j,a[105][105];
  cin>>n;
  for(i=1;i<=n;++i)
  for(j=1;j<=i;++j)
  cin>>a[i][j];
  for(i=n-1;i>=1;--i)//从第二行开始
  for(j=1;j<=i;++j)
  a[i][j]+=max(a[i+1][j],a[i+1][j+1]);
  cout<<a[1][1];
  return 0;
}

动态规划初步 可以用逆推做

#include<bits/stdc++.h>

using namespace std;

long n,a[1005][1005],i,j,ma,f[1005][1005];

long read()//快读

{

long x=0,f=1; 

char ch=getchar(); 

while(ch<'0'||ch>'9'){
    
     if(ch=='-')f=-1; 

     ch=getchar(); 
}

while(ch>='0'&&ch<='9') { 

    x=x10+(ch-'0');

    ch=getchar(); 
    
}

 return xf; 

}

void write(long x)

{//快输 if(x<0){

putchar('-')；

write(-x);

return;

}

if(x>=10)write(x/10);

putchar(x%10+'0');

}

int main()

{ n=read();

for(i=1;i<=n;i++) 

    for(j=1;j<=i;j++) 
    
        a[i][j]=read();//输入 
for(i=n;i>0;i--) 

    for(j=1;j<=i;j++) { 
        
        ma=a[i][j]+max(f[i+1][j],f[i+1][j+1]);//加上下一层的正下的下右
        
        f[i][j]=max(f[i][j],ma); //找最大
    }

write(f[1][1]);//输出第一层第一个 

return 0; 

}