c++动态规划

解题思路:

这是动态规划的基本题目，首先确定b[j][k]是表示从[1][1]（顶部）到a[j][k]所累加的最大值，而b[j][k]是从a[j-1][k]或者a[j-1][k-1]到来的，只要使用max函数确定这两个数谁大就可以确定这个点的最大值，依次类推。最后确定最底一行的最大值就是要求的值。

注意事项:
此题中的左下是正下的意思，不是左边的下方。
参考代码:

#include<iostream>

#include<cmath>

using namespace std;

int main()

{

int a[101][101]={0},b[101][101]={0},i,n,m;//a[j][k]表示初始这个点的值，b[j][k]表示到这个点的最大值。

cin>>n;//n表示测试的次数

int c[n+1]={0};

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

{

cin>>m;

for(int j=1;j<=m;j++)//输入数据 

{

for(int k=1;k<=j;k++)

{

cin>>a[j][k];

}

}

for(int j=2;j<=m;j++)//注意最左边要单独计算，因为只能一直向下走要单独计算。

{

b[j][1]=a[j][1]+b[j-1][1];

}

for(int j=2;j<=m;j++)//同理最右边也要单独计算。

{

b[j][j]=b[j-1][j-1]+a[j][j];

}

for(int j=1;j<=m;j++) 

{

for(int k=1;k<=j;k++)

{

b[j][k]=max(b[j-1][k]+a[j][k],b[j-1][k-1]+a[j][k]);

}

}

for(int j=1;j<=m;j++)

{

c[i]=max(c[i],b[m][j]);//将每次测试的最大值输入到数组中。

}

}

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

{

cout<<c[i]<<endl;

}

return 0;

}