Project Euler 18 Maximum path sum I（ DP and 记忆化搜索）

题意：****求从三角形顶端出发到达底部，所能够得到的最大路径和

方法一：记忆化搜索

/*************************************************************************

    > File Name: euler018t2.c

    > Author:    WArobot

    > Blog:      http://www.cnblogs.com/WArobot/

    > Created Time: 2017年06月28日 星期三 11时01分01秒

 ************************************************************************/

#include <stdio.h>

#include <inttypes.h>

#define MAX_N 15

int32_t Mat[MAX_N][MAX_N];

int32_t f[MAX_N][MAX_N];					// f[x][y] 代表从点 (x,y) 到最底端的最长路径长度

int32_t DFS(int32_t x , int32_t y) {		// 搜索点(x,y)下方路径中的最大值

	if (x + 1 == MAX_N)	return Mat[x][y];

	if (f[x][y] != 0  )	return f[x][y];		// 记忆化，如果(x,y)已经求得下面路径中的最大值，则返回上次记忆的最长路径

	int32_t ans1 , ans2;

	ans1 = DFS(x + 1 , y) + Mat[x][y];

	ans2 = DFS(x + 1 , y + 1) + Mat[x][y];

	f[x][y] = ans1 > ans2 ? ans1 : ans2;	// 记忆化部分

	return f[x][y];

}

int32_t main() {

	freopen("euler018input.txt","r",stdin);

	for (int32_t i = 0 ; i < MAX_N ; i++) {

		for (int32_t j = 0 ; j <= i ; j++) {

			scanf("%d",&Mat[i][j]);

		}

	}

	int32_t ret = DFS(0,0);

	printf("%d\n",ret);

	return 0;

}

方法二：DP

/*************************************************************************

    > File Name: euler018.cpp

    > Author:    WArobot

    > Blog:      http://www.cnblogs.com/WArobot/

    > Created Time: 2017年05月17日 星期三 22时21分32秒

 ************************************************************************/

#include<bits/stdc++.h>

using namespace std;

const int MAX_N = 15;

int mat[MAX_N + 4][MAX_N + 4];

int main(){

	memset(mat,0,sizeof(mat));

	freopen("euler018input.txt","r",stdin);

	for(int i = 0 ; i < MAX_N ; i++)

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

	printf("mat[1][1] = %d\n",mat[1][1]);

	for(int i = MAX_N-1-1 ; i >= 0 ; i--){

		for(int j = 0 ; j <= i ; j++){

			mat[i][j] += max(mat[i+1][j] , mat[i+1][j+1]);

		}

	}

	printf("ans = %d\n",mat[0][0]);

	return 0;

}

巴特西

Project Euler 18 Maximum path sum I（ DP and 记忆化搜索）

最新文章

热门文章

巴特西

Project Euler 18 Maximum path sum I（ DP and 记忆化搜索 ）

最新文章

热门文章

Project Euler 18 Maximum path sum I（ DP and 记忆化搜索）