| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 50977 | Accepted: 30888 |
Description
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
(Figure 1)
Input
Output
Sample Input
5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5
Sample Output
30
Source
1 #include <cstdio> 2 #include <cstring> 3 #include <cmath> 4 #include <iostream> 5 using namespace std; 6 7 int dp[105][105]; 8 int f[105][105]; 9 10 int func(int n) 11 { 12 for(int i=n-1;i>=1;i--) 13 { 14 for(int j=1;j<=i;j++) 15 { 16 dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+f[i][j]; 17 } 18 } 19 return dp[1][1]; 20 } 21 int main() 22 { 23 int n; 24 while(~scanf("%d",&n)) 25 { 26 for(int i=1;i<=n;i++) 27 { 28 for(int j=1;j<=i;j++) 29 { 30 scanf("%d",&f[i][j]); 31 } 32 } 33 for(int i=1;i<=n;i++) dp[n][i]=f[n][i]; 34 printf("%d\n",func(n)); 35 } 36 37 return 0; 38 }
DP的递归写法
1 #include <cstdio> 2 #include <cstring> 3 #include <cmath> 4 #include <iostream> 5 using namespace std; 6 7 int dp[105][105]; 8 int f[105][105]; 9 int n; 10 11 int func(int i,int j) 12 { 13 if(i==n) return dp[i][j]=f[i][j]; 14 if(dp[i][j]!=-1) return dp[i][j]; 15 return dp[i][j]=max(func(i+1,j),func(i+1,j+1))+f[i][j]; 16 17 } 18 int main() 19 { 20 21 while(~scanf("%d",&n)) 22 { 23 memset(dp,-1,sizeof(dp)); 24 for(int i=1;i<=n;i++) 25 { 26 for(int j=1;j<=i;j++) 27 { 28 scanf("%d",&f[i][j]); 29 } 30 } 31 32 printf("%d\n",func(1,1)); 33 } 34 35 return 0; 36 }
原文：http://www.cnblogs.com/moxi-543494/p/7417050.html