★1.5.1 Number Triangles 数字金字塔

一、题目描述

二、解题思路

第一眼见到这个题，我们就要考虑这个题是什么类型？会用到什么算法？一般稍微有点算法基础的就知道，这是一个动态规划问题。

在动态规划问题中，最重要的就是分析你所要关注的状态是什么，然而写出状态转移方程。在状态转移方程中，我们要清楚的明白状态方程的状态表达式是什么含义？是如何从上一状态转移到当前状态的？

对于本题，这是一个简单的动态规划问题（虽然简单，但我还是没想出来，大脑一片混乱。。。）。设f[i,j]表示到达第i层第j个最大的分数。 状态转移方程： f[i,j]=Max{f[i+1,j],f[i+1,j+1]}+a[i,j] (1<=i<=n-1,1<=j<=i)我们只需要知道下层的情况，所以可以用滚动数组来记录（降低空间复杂度），时间复杂度O(n^2)，空间复杂度O(n)。（引自http://www.nocow.cn/index.php/USACO/numtri）

下面是我的源代码

#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;

int max(int a,int b){
	return a>b ? a:b;
}
int num[1000][1000],f[1000];

int main(){
	freopen("numtri.in","r",stdin);
	//freopen("numtri.out","w",stdout);

	int R;
	int i,j;
	scanf("%d",&R);
	for (i=0;i<R;i++)
		for(j=0;j<i+1;j++)
			scanf("%d",&num[i][j]);

	for (i=0;i<R;i++)
		f[i]=num[R-1][i];

	for (i=R-1-1;i>=0;i--)
		for (j=0;j<=i;j++)
		{
			f[j]=max(f[j],f[j+1])+num[i][j];}

cout<<f[0]<<endl;

return 0;
}

1.5.1 Number Triangles 数字金字塔