学步园

/*DP的经典入门题，我用三种方法重做一遍
1.递归计算
2.递推计算
3.记忆化搜索
*/

//方法一：
#include <stdio.h>
int a[100][100], N;
int d( int i, int j )
{
	return a[i][j] + ( i == N ? 0 :  d(i+1, j) > d(i+1, j+1) ? d(i+1, j) : d(i+1, j+1)  );
}
int main()
{
	int i, j;
	scanf( "%d", &N );
	for( i = 1; i <= N; i++ )
		for( j = 1; j <= i; j++ )
			scanf( "%d", &a[i][j] );
	printf( "%d\n", d(1, 1) );
	return 0;
}

//方法二：
#include <stdio.h>
int d[100][100], a[100][100];
int main()
{
	int i,j,N;
	scanf( "%d", &N );
	for( i = 1; i <= N; i++ )
		for( j = 1; j <= i; j++ )
				scanf( "%d", &a[i][j] );
/*--------------------------递推数组---------------*/
	for( j = 1; j <= N; j++ ) d[N][j] = a[N][j];
	for( i = N-1; i >=1; i-- )
		for( j = 1; j <= i; j++ )
			d[i][j] = a[i][j] + ( d[i+1][j] > d[i+1][j+1] ? d[i+1][j] : d[i+1][j+1] );
	printf( "%d\n", d[1][1] );
	return 0;
}

//方法三:
#include <stdio.h>
#include <string.h>
int a[100][100];
int num[100][100];	//标记数组，判断是否被搜索
int N;
int d( int i, int j )
{
	if( num[i][j] >= 0 ) return num[i][j];
	return num[i][j] = a[i][j] + ( i == N ? 0 : d(i+1, j) > d(i+1, j+1) ? d(i+1, j) : d(i+1, j+1) );
	// return a = b;   C语言中赋值语句是有返回值的,返回a 的值，也就是b
}
int main()
{
	int i, j, N;  
    scanf( "%d", &N );  
    for( i = 1; i <= N; i++ )  
        for( j = 1; j <= i; j++ )  
            scanf( "%d", &a[i][j] ); 
	memset( num, -1, sizeof(num) );
	printf( "%d\n", d(1,1) );
	return 0;
}