最大矩阵成本路径，

debugcn 发表于 Dev

小憩

我正在尝试通过动态编程解决此问题：

您将得到n行和m列的矩阵。每个元素都有一个数字，兔子停留在左上角。

计算最大和，以使兔子到达底部元素并且只允许移动两个：

向右两步，向下两步（x +2，y +1）；
下移两步，向右移1步（x +1，y +2）；

输入：

第一行包含两个自然数n和m（1≤n ，m≤10 ³）–矩阵的行和列数。

接下来的n行包含m个数字-矩阵元素的值。

左上角的坐标是（1，1），右下角的–（n，m）。

输出：

使兔子达到右下角的最大和。如果无法到达右下角，则输出-

输入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循环内的计算是否正确？

亭子

首先要意识到，这是更常见问题的一种变体，其中有效的“移动”是“右”和“下”。可以映射到它。

如果可视化有效移动可以到达的点，则可以在矩阵中获得以下模式：

x - - - - - - - -
- - x - - - - - - 
- x - - x - - - -
- - - x - - x - -
- - x - - x - - x
- - - - x - - x -
- - - x - - x - -
- - - - - x - - x

因此，实际上许多矩阵值甚至都不起作用-无法达到它们。如果我们还从无法达到目标的位置移除了斑点，那么我们得到了。我还使用一些不同的字母来突出显示属性：

x - - - - - - - -
- - x - - - - - - 
- y - - x - - - -
- - - y - - x - -
- - z - - y - - -
- - - - z - - y -
- - - - - - z - -
- - - - - - - - z

如果它有一个“ x”，则只能通过（+ 2，+ 1）种移动方式到达该位置。如果它的位置为“ y”，则需要一种（+ 1，+ 2）的移动方式；如果位置为“ z”，则需要其中的两种移动方式。

这是一个可以转换为以下形状的形状：

x x x x
y y y y 
z z z z

转换这样的问题并在该配置中解决它会很有趣。

在这里，我将不再追求这个想法。

您的代码当前缺少有关何时输出的测试-。

我们需要测试是否可以到达目标细胞。您可以看到，如果某个点的x和y坐标之和（从零开始）不是3的倍数，则无法到达该点。还有一些点的总和是3的倍数，但仍不存在触手可及。这是其中一个坐标至少是另一个坐标的两倍（标有星号）的地方：

x - - * - - * - -
- - x - - * - - * 
- y - - x - - * -
* - - y - - x - -
- - z - - y - - -
- * - - z - - y -
* - - - - - z - -
- - * - - - - - z

因此，您应该将此行添加到代码中：

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，与第一个条件无关。

对于初始化部分：不必res使用-1值初始化矩阵。无论如何，您都不希望在计算中包含-1。您将要避免依赖这些值。相反，您必须为动态编程工作初始化一个起点：

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];
}

请注意，循环的停止条件会消除目标无法触及的位置。

在另一个方向上执行相同的操作：

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个可能的地点来自。因此，通过从以下两个位置中选择最大值来走所有其他路径：

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];
    }
}

最后输出结果：