数字三角形问题.cpp

动态规划解一系列经典问题

#include<iostream> 
using namespace std; 
int a[101][101]; 
int N; 
int fmax(int a,int b) 
{ 
return a>b?a:b; 
} 
int f(int row,int col)//f(0,0)即为所要求的值,row表示行数 
{ 
//f(0,0)=max(f(1,0),f(1,1))+a[0][0] 
if(row==N-2)//倒数第二层 
return fmax(a[row+1][col],a[row+1][col+1])+a[row][col]; 
return fmax(f(row+1,col),f(row+1,col+1))+a[row][col]; 
} 
int main() 
{ 
/*输入三角形的行数*/ 
cin>>N; 
/*输入每行的数*/ 
for(int i=0;i<N;i++) 
for(int j=0;j<i+1;j++) 
cin>>a[i][j]; 
cout<<f(0,0)<<endl; 
return 0; 
}