最大矩阵成本路径， [英] maximum matrix cost path,
问题描述
我正在尝试通过动态编程来解决此问题：
I am trying to solve this problem through dynamic programming:
您将得到一个由 n 行和 m 列。每个元素都有一个数字
，兔子位于左上角。
You are given a matrix of n rows and m columns. Every element has a number and the rabbit staying at the top left element.
计算最大和，以使兔子到达底部元素，而
只有两个允许移动：
Calculate the maximum sum such that the rabbit gets to the bottom element and only two moved allowed:
向右两步，向下两步（ x +2， y +1）;
向下两步，向右1步（ x +1， y +2）;
Two steps right and 1 step down (x+2, y+1);
Two steps down and 1 step to the right (x+1, y+2);
输入：
第一行包含两个自然数 n 和 m （ 1≤n，m≤ 10 3 ）–矩阵的行和列的数量。
The first line contains two naturals n and m (1 ≤ n, m ≤ 103) – the quantity of rows and columns of the matrix.
接下来的 n 行包含 m 数字–矩阵
元素的值。
The next n lines contain m numbers – the values of the matrix elements.
左上角的坐标为（1，1），右下角的
角为– （ n ， m ）。
The top left coordinates are (1, 1), the bottom right corner’s – (n, m).
输出：
最大和，以使兔子到达右下角。
如果无法到达右下角，则输出-
The maximum sum so that the rabbit reaches the bottom right.
If bottom right can not be reached, output -
输入1：
3 3
5 0 0
0 1 2
1 0 1
输出1：
-
输入2：
4 4
5 2 1 0
1 0 0 0
2 1 3 0
0 0 1 7
输出2：
13
此代码我尝试开发：
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
using namespace std;
void findMaxSum(int *a[], int r, int c)
{
int **res = new int*[r];
for (int i = 0; i < r; i++) {
res[i] = new int[c];
for (int j = 0; j < c; j++)
res[i][j] = -1;
}
for (int i = 0; i < r-1; i++) {
for (int j = i; j < c-1; j++) {
res[i + 1][j + 2] = max(a[i][j] + a[i + 1][j + 2], res[i + 1][j + 2]);
res[i + 2][j + 1] = max(a[i][j] + a[i + 2][j + 1], res[i + 2][j + 1]);
}
}
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++)
cout << res[i][j] << " ";
cout << endl;
}
delete[] res;
}
int main() {
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
int r, c;
cin >> r >> c;
int **a = new int*[r];
for (int i = 0; i < r; i++) {
a[i] = new int[c];
}
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++)
cin >> a[i][j];
}
findMaxSum(a, r, c);
delete[] a;
return 0;
}
这是方法吗，for循环内的计算是否正确？
Is this the approach, are the calculations inside for loops correct?
推荐答案
首先意识到，这是常见问题，其中有效的动作是向右和向下。可以映射到它。
First realise that this is a variant of the more common problem where valid "moves" are "right" and "down". It can be mapped to it.
如果可视化有效移动可以到达的点，则可以在矩阵中得到以下模式：
If you visualise the spots that can be reached by valid moves, you get this pattern in the matrix:
x - - - - - - - -
- - x - - - - - -
- x - - x - - - -
- - - x - - x - -
- - x - - x - - x
- - - - x - - x -
- - - x - - x - -
- - - - - x - - x
实际上很多矩阵价值观甚至不起作用-无法实现。如果我们还删除了无法到达 target 的位置，那么我们可以做到这一点。我还使用一些不同的字母突出显示属性：
So actually many matrix values don't even play a role -- they cannot be reached. If we also remove the spots from where the target cannot be reached, then we get this. I also use some different letters to highlight a property:
x - - - - - - - -
- - x - - - - - -
- y - - x - - - -
- - - y - - x - -
- - z - - y - - -
- - - - z - - y -
- - - - - - z - -
- - - - - - - - z
如果有 x，则只能通过（+ 2，+ 1）种移动方式来达到该位置。如果它有一个 y，则需要一种（+ 1，+ 2）的移动，而如果有一个 z，则需要其中的两个。
Where it has an "x", the spot can be reached via (+2,+1) type of moves only. Where it has an "y", it needs one (+1,+2) type of move, and where there is a "z", two of those are needed.
这是可以转换为以下形状的形状：
This is a shape that can be translated to this shape:
x x x x
y y y y
z z z z
翻译这样的问题并在该配置中解决它会很有趣。
It would be interesting to translate the problem like that, and solve it in that configuration.
在这里我不会继续讲这个想法。
I will not pursue that idea here.
您的代码当前缺少何时输出的测试- 。
Your code is currently missing the test for when to output -.
我们需要测试是否可以到达目标单元格。您可以看到，如果某个点的x和y坐标之和（从零开始）不是3的倍数，则无法到达该点。还有一些点的总和是3的倍数，但仍不存在触手可及。这是其中一个坐标至少是另一个坐标的两倍（标有星号）的地方：
We need to test whether the target cell can be reached. You can see that a spot cannot be reached if the sum of its x and y coordinate (when zero-based) is not a multiple of 3. And there are also spots where this sum is a multiple of 3, but which are still out of reach. This is where one of the coordinates is at least the double of the other coordinate (marked with an asterisk):
x - - * - - * - -
- - x - - * - - *
- y - - x - - * -
* - - y - - x - -
- - z - - y - - -
- * - - z - - y -
* - - - - - z - -
- - * - - - - - z
因此您应该在代码中添加以下行：
So you should add this line to your code:
if ((r+c) % 3 != 2 || r*2 < c || c*2 < r) {
cout << "-";
return;
}
（r + c）％3！= 2 源自（r-1 + c-1）％3！= 0 和 r * 2< c 源自（r-1）* 2< （c-1）* 2 差异为1，与第一个条件无关。
(r+c) % 3 != 2 is derived from (r-1 + c-1) % 3 != 0, and r*2 < c is derived from (r-1)*2 < (c-1)*2 with a difference of 1, which is not relevant given the first condition.
用于初始化部分：不必使用-1值初始化 res 矩阵。无论如何，您都不希望在计算中包含-1。您将避免依赖于这些值。相反，您必须初始化动态编程的起点才能工作：
For the initialisation part: it is not necessary to initialise the res matrix with -1 values. You wouldn't want to involve a -1 in your calculation anyway. You'll want to avoid relying on such values. Instead you must initialise a starting point for the dynamic programming to work:
res[0][0] = a[0][0];
然后，对于实际的引导：
for (int i = 2, j = 1; (r-i)*2 > c-j; i+=2, j++) {
res[i][j] = res[i-2][j-1] + a[i][j];
}
请注意，循环的停止条件会消除目标离开的位置
Note that the loop's stop-condition eliminates spots from where the target would be out of reach.
在另一个方向上做同样的事情：
Do the same in the other direction:
for (int i = 1, j = 2; (c-j)*2 > r-i; i++, j+=2) {
res[i][j] = res[i-1][j-2] + a[i][j];
}
现在，您已经为动态编程的主要部分设置了外部边界 。其他有效地点将始终有2个可能的地点来自。因此，通过从两个点中选择最大值来走所有其他路径：
Now you have set up the "outer borders" for the main dynamic programming part. The other valid spots will always have 2 possible spots to come from. So take all other paths by choosing the maximum value from the two spots you could come from:
for (int i = 2, j = 1; (r-i)*2 > c-j; i+=2, j++) {
for (int m = i + 1, n = j + 2; (c-n)*2 > r-m; m++, n += 2) {
res[m][n] = max(res[m-1][n-2], res[m-2][n-1]) + a[m][n];
}
}
最后输出结果：
cout << res[r-1][c-1];
NB：我希望函数返回该值，然后让 main 完成所有I / O。
NB: I would prefer a function to return that value, and let main do all the I/O.
这篇关于最大矩阵成本路径，的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
