前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >寻宝路线(动态规划)

寻宝路线(动态规划)

作者头像
砖业洋__
发布2023-05-06 16:45:05
880
发布2023-05-06 16:45:05
举报
文章被收录于专栏:博客迁移同步
代码语言:javascript
复制
#include <stdio.h>
#define MAX 101
int map[MAX][MAX];
int S[MAX][MAX];
int F[MAX][MAX];

int m, n;
int max(int a, int b)
{
	return a > b ? a : b;
}
int dp(int i, int j)
{
	if (i < 0 || j < 0)	return -10000;
	if (F[i][j])	return F[i][j]; // F[i][j]存放的就是从右下角到达该点捡起宝物价值最大值,最后F[0][0]即为所求
	if (i == m - 1 && j == n - 1)//ij条件交集放前面 
	{
		return F[i][j] = map[i][j];
	}
	else if (i == m - 1) // 到达底端,就只能往右走
	{
		return F[i][j] = map[i][j] + dp(i, j + 1);
	}
	else if (j == n - 1) // 到达右端,只能往下走
	{
		return F[i][j] = map[i][j] + dp(i + 1, j);
	}
	else // 否则在这一点能够获得的最大价值就是该点的宝物价值加上往右或者往下走能够获得的最大价值
	{
		return F[i][j] = map[i][j] + max(dp(i + 1, j), dp(i, j + 1));
	}
}

int s(int i, int j)
{
	if (i < 0 || j < 0)	return -10000;
	if (S[i][j])	return S[i][j];
	if (i == m - 1 || j == n - 1)//到边界,只能往右或者往下,只有唯一路径,不用继续走了 
	{
		return S[i][j] = 1;
	}
	else
	{
		if (F[i][j] == map[i][j] + F[i][j + 1])	S[i][j] += s(i, j + 1);
		if (F[i][j] == map[i][j] + F[i + 1][j])	S[i][j] += s(i + 1, j);
		return S[i][j];
	}
}

int main()
{
	int i, j;
	scanf("%d %d", &m, &n);
	for (i = 0; i < m; ++i)
	{
		for (j = 0; j < n; ++j)
		{
			scanf("%d", &map[i][j]);
		}
	}
	printf("%d ", dp(0, 0));

  /*putchar('\n');
	putchar('\n');
	printf("便于理解,打印F数组,记录最值:\n");
	for (i = 0; i < m; ++i)
	{
		for (j = 0; j < n; ++j)
		{
			printf("%d ", F[i][j]);
		}
		putchar('\n');
	}
	putchar('\n');
	putchar('\n');*/

	printf("%d\n",s(0,0));

	/*putchar('\n');
	putchar('\n');
	printf("便于理解,打印S数组,记录路径最大值:\n");
	for (i = 0; i < m; ++i)
	{
		for (j = 0; j < n; ++j)
		{
			printf("%d ", S[i][j]);
		}
		putchar('\n');
	}*/

	return 0;
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2018-03-21,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档