POJ 3176 Cow Bowling

大致题意：

输入一个n层的三角形，第i层有i个数，求从第1层到第n层的所有路线中，权值之和最大的路线。

规定：第i层的某个数只能连线走到第i+1层中与它位置相邻的两个数中的一个。

f[i][j]：表示第 i 行第 j 列到最后一行的最大权值和；

状态方程：

f[i][j]=w[i][j]+max(f[i+1][j],f[i+1][j+1]);

/ Time 157ms; Memory 1236K 

// Time 157ms; Memory 1236K[cpp] view plaincopyprint?#include<iostream>  
using namespace std; 
int max(int a,int b) 
{ 
    return a>b?a:b; 
} 
int main() 
{ 
    int i,j,n,w[355][355],f[355][355]; 
    cin>>n; 
    for(i=0;i<n;i++) 
    { 
        for(j=0;j<=i;j++) cin>>w[i][j]; 
    } 
    for(i=0;i<n;i++) f[n-1][i]=w[n-1][i]; 
    for(i=n-2;i>=0;i--) 
    { 
        for(j=0;j<=i;j++) f[i][j]=w[i][j]+max(f[i+1][j],f[i+1][j+1]); 
    } 
    cout<<f[0][0]<<endl; 
    return 0; 
} 

#include<iostream>
using namespace std;
int max(int a,int b)
{
 return a>b?a:b;
}
int main()
{
 int i,j,n,w[355][355],f[355][355];
 cin>>n;
 for(i=0;i<n;i++)
 {
  for(j=0;j<=i;j++) cin>>w[i][j];
 }
 for(i=0;i<n;i++) f[n-1][i]=w[n-1][i];
 for(i=n-2;i>=0;i--)
 {
  for(j=0;j<=i;j++) f[i][j]=w[i][j]+max(f[i+1][j],f[i+1][j+1]);
 }
 cout<<f[0][0]<<endl;
 return 0;
}

补充：软件开发 , C++ ,