1163 动态规划 解题报告

http://acm.pku.edu.cn/JudgeOnline/problem?id=1163

7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

题目要求重第一个元素到最后一排中相加和最大值，用动态规划解，由于没有求路径，故无需另外开辟一个数组，直接在原有的数组上进行操作即可，

#include<iostream>
using namespace std;

const int Max=101;
int b[Max][Max];
int max( int a,int b)
{
if( a>b)
return a;
else return b;
}
int main()
{
//freopen("in.txt","r",stdin);
int m,i,j;
cin>>m;
for( i=1; i<=m; i++)
for( j=1; j<=i; j++)
cin>>b[i][j];
for( i=m-1; i>=1; i--)
for( j=1; j<=i; j++)
b[i][j]=max(b[i+1][j],b[i+1][j+1])+b[i][j];

cout<<b[1][1]<<endl;
return 0;
}