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;
}