POJ 1163 The Triangle C++版

发表于 更新于

题目链接：http://poj.org/problem?id=1163

这个题目一个数字金字塔，求由上到下，经过的数字和最大为多少，其实本身看着简单的很，第一想法肯定是递归，必定这样的题目我以前做过，老师也是教的递归做法，由上到下，将问题分解为若干个小问题，这样利用一个求值型函数既可解决问题。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
using namespace std;

int n,num[100][100];

int DFS(int i, int j)
{
	if(i==n)
		return num[i][j];
	else if (DFS(i+1,j)>DFS(i+1,j+1))
		return DFS(i+1,j)+num[i][j];
	else
		return DFS(i+1,j+1)+num[i][j];
}
int main()
{
	cin>>n;
	for(int i=1; i<=n; i++)
		for(int k=1; k<=i; k++)
			cin>>num[i][k] ;
	cout<<DFS(1,1)<<endl;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/*Problem: 1163		User: awq123
**Memory: 292K		Time: 0MS
**Language: C++		Result: Accepted
*/
#include <iostream>
using namespace std;

int main()
{
	int i,j,n,num[100][100];
	cin>>n;
	for(i=0; i<n; i++)
		for(j=0; j<=i; j++)
			cin>>num[i][j] ;
	for(i=n-2;i>=0;i--)
		for(j=0;j<=i;j++)
			num[i][j]+=(num[i+1][j]>num[i+1][j+1])?num[i+1][j]:num[i+1][j+1];
	cout<<num[0][0]<<endl;
}