PKU算法基礎（二）Exp6.1 數字三角形 //POJ1163

POJ1163

動态規劃。

首先是正着來，i行j列的數字的上級可以是左對角，也可以是右對角，是以取較大的那個加上本身就可以得到到達該數時的最大和。

将整個數組初始化為零，求較大值時就不用考慮越界的情況。

很容易寫出代碼（見下面）

但是正向寫并不夠優秀，因為需要考慮(i+1,j-1)位置的越界問題，再就是最後還要周遊最後一排的元素去找最大值，這是完全沒有必要的消耗。

考慮倒着來做，最後一排作為出發點向前看，每一點的result值表示從最後一排到該點的最大數，這樣最後隻需要列印result[0][0]即可。

倒着（更優）

#include <iostream>
int n;
int triangle[100][100]={0};
int result[100][100]={0};

void process();

int main(int argc, char const *argv[])
{
	cin>>n;
	int i,j;
	for(i=0;i<n;++i)
		for(j=0;j<=i;++j)
			cin>>triangle[i][j];
	process();
	cout>>result[0][0];
	return 0;
}

void process()
{
	int i,j;
	for(j=0,i=n-1;j<n;++j)
		result[i][j]=triangle[i][j];
//最後一排對拷
	for(i=n-2;i>=0;--i)
		for(j=0;j<n;++j)
			result[i][j]=triangle[i][j]+max(result[i+1][j],result[i+1][j+1]);
//從最後一排向前推，動态規劃
}

           

正着（思路簡單）

#include <iostream>
using namespace std;
int triangle[100][101]={0};
int result[100][101]={0};
int n;

void process();
int main(int argc, char const *argv[])
{
	cin>>n;
	int i,j;
	for(i=0;i<n;++i)
		for(j=0;j<=i;++j)
			cin>>triangle[i][j];
	process();
	int max_result=result[n-1][0];
	for(i=1;i<n;++i)
		if(result[n-1][i]>max_result)
			max_result=result[n-1][i];
	cout<<max_result;
	return 0;
}

void process()
{
	result[0][0]=triangle[0][0];
	int ld,rd;
	for(int i=1;i<n;++i)
		for(int j=0;j<=i;++j)
			{
				ld=(j==0)?0:result[i-1][j-1];
				rd=result[i-1][j];
				//ld->left_diagonal，防止j-1越界
				result[i][j]=max(ld,rd)+triangle[i][j];
			}
}