打败魔王（这是2022中兴捧月打榜的一道题）

• 1、题目描述
• 2、解法1
• 3、解法2
• 4、解法3

小明和小红是两位魔法师，他们一起在一张N*N的方格地图上冒险（N<=9）去击败魔王，地图中的方格代表他们所走的路径，方格中的正整数代表可获得的法力值，而其他的方格中的数字为0代表无法获得法力值，如下图所示（见样例）：

他们二人从图上的起点出发，为了更快的打败魔王，他只能向右或者向下前进，直到到达下方的魔王城。在走过的路上，他们能够获得地图里的数字（获取后地图中将变为数字0）变为法力值。小明先从起点出发走到魔王城，然后小红再出发到达魔王城，为了更好的对抗魔王，请你帮帮2位魔法师使其获得的法力值为最大。

输入描述：

第一行为1个整数N(0

输出描述：

只需要输出一个整数，表示小明和小红能获得的最大法力值的和。

样例1：

输入：
7
2 1 12
2 5 8
2 6 6
3 3 5
4 3 13
6 6 5
7 2 1
0 0 0
输出：
49

样例2：

输入：
5
1 1 5
1 3 6
2 5 6
4 2 13
5 1 5
0 0 0
输出：
30

贪心：进行两次动态规划，每次取最大值。这个方法无法获取全局最大，要获取全局最大请继续向下读

动态规划

• 1、确定dp数组极其含义
  dp[i][j]表示坐标为i,j的位置最大法力为dp[i][j].
• 2、确定递推公式
  dp[i][j]可由两个方向进行得到，一个是dp[i-1][j],另一个是dp[i][j-1]，因为本题要获取最大法力，因此：dp[i][j]=max(dp[i-1][j],dp[i][j-1])+mp[i][j]
• 3、如何初始化
  因为只有两个方向，因此在边缘上对其进行累加即可。

完整cpp代码：

#include
#include
#include
#include
#include
using namespace std;

void my_dp(int N,vector> &dp, vector>& mp, vector>& mp_b)
{
	for (int i = 1; i < N; i++)
	{
		for (int j = 1; j < N; j++)
		{
			int a = dp[i - 1][j];
			int b = dp[i][j - 1];
			if (a >= b) //选择向右的路径
			{
				dp[i][j] = a + mp[i][j]; // 计算此时的最大法力值

				mp[i - 1][j] = 0; // 由题意，我们走了这个地方就需要将该点的法力值清0
				for (int p = 0; p < j; p++)// 那么该点上面的数据我们需要将其保持恒定不变，从备份图中拷贝过来
					mp[i][p] = mp_b[i][p];

			}
			else
			{
				dp[i][j] = b + mp[i][j];// 和上面一样
				mp[i][j - 1] = 0;
				for (int p = 0; p < i; p++)
					mp[p][j] = mp_b[p][j];

			}
		}
	}
}

void my_Init(int N,vector> &dp, vector> mp)
{
	int tem = 0;
	for (int i = 0; i < N; i++) // 进行初始化，因为只能向下和向右，因此边缘为边缘数据的累和
	{
		tem += mp[i][0];
		dp[i][0] = tem;
	}
	tem = 0;
	for (int i = 0; i < N; i++)
	{
		tem += mp[0][i];
		dp[0][i] = tem;
	}
}
int main() {
	int N = 0;
	cin >> N;
	vector> mp(N,vector(N,0));//构建地图
	while (true) // 数据输入
	{
		int x, y, z;
		cin >> x >> y >> z;

		if (x == 0 && y == 0 && z == 0)
			break;
		mp[x-1][y-1] = z;
	}
	vector> mp_b = mp; // 进行地图备份
	// dp[i][j] 表示位置在i和j处能获得的最大法力
	// dp[i][j] = max(dp[i-1][j],dp[i][j-1])
	// 创建dp数组
	vector> dp(N,vector(N,0));
	vector> dp1(N, vector(N, 0));
	// 进行第一个人dp数组初始化
	my_Init(N,dp,mp);
	//进行第一个人dp
	my_dp(N,dp,mp,mp_b);

	mp[0][0] = 0;
	mp[N - 1][N - 1] = 0;  // 上面是从1,1点开始的，我们需要手动将起点和重点清0

	// 第二轮开始，从新初始化dp1
	my_Init(N, dp1, mp);
	// 进行第二个人的dp
	my_dp(N, dp1, mp, mp_b);

	// 两人最大法力值为两个dp数组的和
	cout << dp[N-1][N-1]+dp1[N-1][N-1] << endl;

	
}

该方法只能达到局部最优，但无法实现全局最优，如这位网友（ m0_49301123）举的一个例子：

0 0 0 0 0
0 0 5 0 0
0 13 0 0 0
0 0 0 8 0
0 1 0 0 0
两次分别取最大值会是第一次13+8=21，第二次5，总21+5=26
而实际上应该是第一次13+1=14，第二次5+8=13，总14+13=27

使用上面方法就无法进行实现。

使用回溯进行深搜：当第一个人选择了一条路径时，我们在这条路径的基础上在进行第二个人的路径搜索，总的来讲就是深搜在嵌套一层深搜索。但这个方法速度很慢，但能跑出正确结果。

完整cpp代码如下：

#include
#include
#include
#include
#include
using namespace std;

int dx[2] = {1,0};
int dy[2] = {0,1};

int** vis = NULL;
int** vis1 = NULL;
vector> path; // 代表走过的路径的坐标
vector> min_path; //记录最小的路径

vector> path1; // 代表走过的路径的坐标
vector> min_path1; //记录最小的路径

int mi = INT_MIN;

vector> mp_b;  // 地图备份

void dfs1(int x, int y, int dxs, int dxy, vector>& map, int m, int n, int step, vector> ph)
{
	// 函数的出口
	if (x == dxs && y == dxy)
	{
		// 统计这一条路径的中总和路径长度
		int tem = 0;
		for (int i = 0; i < path1.size(); i++)
		{
			tem += map[path1[i].first][path1[i].second];
		}
		// 统计前一条路径和
		 
		for (int i = 0; i < ph.size(); i++)
		{
			tem += mp_b[ph[i].first][ph[i].second];
		}
		  
		// 如果这条路径比前一条还短，那么就进行路径更新
		if (tem >= mi)
		{
			//min_path1 = path1;
			mi = tem;
		}

		return;
	}

	// 进行是个方向进行探索
	for (int i = 0; i < 2; i++)
	{
		int tx = x + dx[i];
		int ty = y + dy[i];
		// 判断是否越界，并且判断是否没有访问
		if (tx >= 0 && ty >= 0 && tx < m && ty < n && !vis1[tx][ty]) // 注意这里tx是小于行，ty是小于列
		{
			// 如果没有走过，并且没有越界，进行探索

			// 首先标记这个点为已经走过
			vis[tx][ty] = 1;
			// 并将这个点压入path中
			path1.push_back(pair(tx, ty));
			dfs1(tx, ty, dxs, dxy, map, m, n, step + 1,ph);
			// 回溯的时候将其取消标记
			vis[tx][ty] = 0;
			// 并将这个点出站
			path1.pop_back();
		}
	}


}

void dfs(int x, int y, int dxs, int dxy, vector> &map, int m, int n, int step)
{
	// 函数的出口
	if (x == dxs && y == dxy)
	{
		// 进行第二个人的dfs
		vis1[0][0] = 1;
		// 将path中的地图清0
		for (int i = 0; i < path.size(); i++)
		{
			map[path[i].first][path[i].second] = 0;
			
		}
		dfs1(0,0,m-1,n-1, map,m,n,0,path);
		for (int w = 0; w < m; w++) // 进行清零 为下一次做准备
		{
			for (int w1 = 0; w1 < n; w1++)
			{
				vis1[w][w1] = 0;
			}
		}
		// 将path中的地图恢复
		for (int i = 0; i < path.size(); i++)
		{
			map[path[i].first][path[i].second] = mp_b[path[i].first][path[i].second];
		}
		 统计这一条路径的中总和路径长度
		//int tem = 0;
		//for (int i = 0; i < path.size(); i++)
		//{
		//	tem += map[path[i].first][path[i].second];
		//}
		 如果这条路径比前一条还短，那么就进行路径更新
		//if (tem >= mi)
		//{
		//	min_path = path;
		//	mi = tem;
		//}

		return;
	}

	// 进行是个方向进行探索
	for (int i = 0; i < 2; i++)
	{
		int tx = x + dx[i];
		int ty = y + dy[i];
		// 判断是否越界，并且判断是否没有访问
		if (tx >= 0 && ty >= 0 && tx < m && ty < n && !vis[tx][ty]) // 注意这里tx是小于行，ty是小于列
		{
			// 如果没有走过，并且没有越界，进行探索

			// 首先标记这个点为已经走过
			vis[tx][ty] = 1;
			// 并将这个点压入path中
			path.push_back(pair(tx, ty));
			dfs(tx, ty, dxs, dxy, map, m, n, step + 1);
			// 回溯的时候将其取消标记
			vis[tx][ty] = 0;
			// 并将这个点出站
			path.pop_back();
		}
	}


}


int** to_arr(int a, int b)
{
	int** map = (int**)malloc(a * sizeof(int*));
	for (int i = 0; i < a; i++)
		map[i] = (int*)malloc(b * sizeof(int)); // 进行内存申请
	// 进行初始化
	for (int i = 0; i < a; i++)
		for (int j = 0; j < b; j++)
			memset(map[i], 0, b * sizeof(int));
	return map;
}
int main() {
	int N = 0;
	cin >> N;
	int m = N ;
	int n = N ;
	vector> mp(N, vector(N, 0));//构建地图
	while (true) // 数据输入
	{
		int x, y, z;
		cin >> x >> y >> z;

		if (x == 0 && y == 0 && z == 0)
			break;
		mp[x - 1][y - 1] = z;
	}
	// 进行备份
	mp_b = mp;

	vis = to_arr(m, n);//申请已访问标记数组
	vis1 = to_arr(m, n);//申请已访问标记数组
	//将0,0标记为已访问
	vis[0][0] = 1;
	path.push_back(pair(0, 0));

	dfs(0, 0, m - 1, n - 1, mp, m, n, 0);

	cout << mi << endl;

	//dfs();


}

上面那种情况测试用例：

输入：
5
2 3 5
3 2 13
4 4 8
5 2 1
0 0 0
输出：
27

总体来讲，上面方法二进行递归嵌套对整个题的开销是非常大的，但是不进行递归又无法获取全局最大，为此，折中的方法是在递归的基础上进行动态规划。

这个方法的时间复杂度较方法1要慢，较方法二要快，但方法1无法获取全局最优，因此，总体上来看，这个方法是目前较好的一种解决方法。如果有同学有更好的解决方法，可以在评论区留言，大家一起学习进步

#include
#include
#include
#include
#include
using namespace std;

int dx[2] = {1,0};
int dy[2] = {0,1};

int** vis = NULL;
int** vis1 = NULL;
vector> path; // 代表走过的路径的坐标
vector> min_path; //记录最小的路径

int mi = INT_MIN;

vector> mp_b;  // 地图备份

void my_dp(int N, vector>& dp, vector>& mp)
{
	for (int i = 1; i < N; i++)
	{
		for (int j = 1; j < N; j++)
		{
			int a = dp[i - 1][j];
			int b = dp[i][j - 1];
			if (a >= b) //选择向右的路径
			{
				dp[i][j] = a + mp[i][j]; // 计算此时的最大法力值
			}
			else
			{
				dp[i][j] = b + mp[i][j];// 和上面一样
			}
		}
	}
}

void my_Init(int N, vector>& dp, vector> mp)
{
	int tem = 0;
	for (int i = 0; i < N; i++) // 进行初始化，因为只能向下和向右，因此边缘为边缘数据的累和
	{
		tem += mp[i][0];
		dp[i][0] = tem;
	}
	tem = 0;
	for (int i = 0; i < N; i++)
	{
		tem += mp[0][i];
		dp[0][i] = tem;
	}
}

void dfs(int x, int y, int dxs, int dxy, vector> &map, int m, int n, int step)
{
	// 函数的出口
	if (x == dxs && y == dxy)
	{
		// 进行第二个人的dfs
		vis1[0][0] = 1;
		// 将path中的地图清0
		for (int i = 0; i < path.size(); i++)
		{
			map[path[i].first][path[i].second] = 0;
			
		}
		vector> dp(m, vector(m, 0));
		my_Init(m, dp, map);
		my_dp(m, dp, map);
		int tem = 0;
		for (int i = 0; i < path.size(); i++)
		{
			tem += mp_b[path[i].first][path[i].second];
		}
		tem = tem + dp[m - 1][m - 1];
		// 如果这条路径比前一条还短，那么就进行路径更新
		if (tem >= mi)
		{
			//min_path1 = path1;
			mi = tem;
		}
		// 将path中的地图恢复
		for (int i = 0; i < path.size(); i++)
		{
			map[path[i].first][path[i].second] = mp_b[path[i].first][path[i].second];
		}
		return;
	}
	// 进行是个方向进行探索
	for (int i = 0; i < 2; i++)
	{
		int tx = x + dx[i];
		int ty = y + dy[i];
		// 判断是否越界，并且判断是否没有访问
		if (tx >= 0 && ty >= 0 && tx < m && ty < n && !vis[tx][ty]) // 注意这里tx是小于行，ty是小于列
		{
			// 如果没有走过，并且没有越界，进行探索

			// 首先标记这个点为已经走过
			vis[tx][ty] = 1;
			// 并将这个点压入path中
			path.push_back(pair(tx, ty));
			dfs(tx, ty, dxs, dxy, map, m, n, step + 1);
			// 回溯的时候将其取消标记
			vis[tx][ty] = 0;
			// 并将这个点出站
			path.pop_back();
		}
	}


}

int** to_arr(int a, int b)
{
	int** map = (int**)malloc(a * sizeof(int*));
	for (int i = 0; i < a; i++)
		map[i] = (int*)malloc(b * sizeof(int)); // 进行内存申请
	// 进行初始化
	for (int i = 0; i < a; i++)
		for (int j = 0; j < b; j++)
			memset(map[i], 0, b * sizeof(int));
	return map;
}
int main() {
	int N = 0;
	cin >> N;
	int m = N ;
	int n = N ;
	vector> mp(N, vector(N, 0));//构建地图
	while (true) // 数据输入
	{
		int x, y, z;
		cin >> x >> y >> z;

		if (x == 0 && y == 0 && z == 0)
			break;
		mp[x - 1][y - 1] = z;
	}
	// 进行备份
	mp_b = mp;

	vis = to_arr(m, n);//申请已访问标记数组
	vis1 = to_arr(m, n);//申请已访问标记数组
	//将0,0标记为已访问
	vis[0][0] = 1;
	path.push_back(pair(0, 0));

	dfs(0, 0, m - 1, n - 1, mp, m, n, 0);

	cout << mi << endl;
}