我正在尝试通过动态编程解决此问题：
您将得到一个n行和m列的矩阵。有一个整数板子上每个单元格上的数字，兔子呆在左上角。
收集可能的最大金额，以便兔子可以移动仅两个方向：
右侧2个单元格，向下1个单元格（x + 2，y + 1）；向下2个单元格，向右1个单元格（x + 1，y + 2）;
输入：
第一行包含两个自然数n和m（1≤n，m≤10 3 –矩阵的行和列的数量。
接下来的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循环内的计算正确吗？
首先意识到，这是更多common problem的变体，其中有效的“移动”是“右”和“下”。可以映射到它。
如果可视化有效移动可以到达的点，则可以在矩阵中获得此模式：
x - - - - - - - -
- - x - - - - - -
- x - - x - - - -
- - - x - - x - -
- - x - - x - - x
- - - - x - - x -
- - - x - - x - -
- - - - - x - - x
因此，实际上许多矩阵值甚至都不起作用-无法达到它们。如果我们还删除了无法到达target的点，那么我们得到了。我还使用一些不同的字母来突出显示属性：
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，这与第一个条件无关。]
对于初始化部分：
不必使用-1值初始化res矩阵。无论如何，您都不希望在计算中包含-1。您将要avoid依赖这些值。相反，您必须初始化动态编程的起点：我将首先仅使用一种移动方式进行移动，然后在该方向上累积成本：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]; } }最后输出结果：
cout << res[r-1][c-1];NB：我希望函数main完成所有I / O。