使用动态规划的矩阵的最小路径 [英] Min Path Through Matrix using Dynamic Programming
问题描述
我现在正在为我的补习班分配作业，目前正在掌握动态编程的窍门.我们当前的任务是给我们一个大小为 m x n 的矩阵，其中m或n至少保证为2.我们可以从任何基本方向从上述位置移动，目标是从索引(0,0)开始，然后必须索引(n-1，m-1)，或者最好是底部矩阵的右角，行程尽可能少.如果这样的路径不可行，我们必须返回-1.这是一个示例:
I'm working on assignment now for my comp class and am currently getting the hang of dynamic programming. Our current task is that we are given a matrix of size m x n, where either m or n is guaranteed to at least be 2. This matrix is filled with various values that dictate how many "steps" we may move from said position in any cardinal direction, with the goal being that we start at index (0,0) and have to make our way to index (n-1,m-1), or, better put, the bottom right corner of the matrix, in the smallest amount of trips as possible. If such a path is not possible, we must return -1. Here's an example:
| 1 | 2 |
|---|---|
| 7 | 5 |
| 6 | 3 |
从左上角到右下角的最小跳跃次数为2，因为我们从(0,0)开始，其值为1，表示我们可以在任何方向上移动1步.然后我们转到(0,1)，它的值为2，我们将使用它来逐步"执行步骤2.两个位置向下到(2,1)，即右下角.总体而言，此旅程经历了两次旅行:一次是从(0,0)到(0,1)，然后是另一次从(0,1)到(2,1).在位置(0,0)时我也可以下降到(0,1)，这毫无价值，但这不会产生任何有用的结果.
The smallest amount of jumps required to get from the top left to the bottom right is 2, since we start at (0,0), which, with value of 1, means we can move 1 step in any direction. We then go to (0,1), which has a value of 2, which we'll use to "step" two positions down into (2,1), which is the bottom right corner. Overall, this journey took two trips: the one from (0,0) to (0,1), and then another from (0,1) to (2,1). It is worth nothing that at position (0,0), I could have also gone down to (0,1), but that wouldn't have resulted in anything useful.
我正在采用一种动态编程方法，其中有一个表用于存储先前计算的值并减少运行时间，并有一个单独的表让我知道我是否已计算出该位置.我的代码如下:
I'm taking a dynamic programming approach, with a table to store previously calculated values and cut down runtime, with a separate table to let me know if I've calculated that position or not. My code is as follows:
private static int [][] dpArray;
private static int [][] solveState;
private static int rowDest;
private static int colDest;
public static int min_moves(int[][] board) {
rowDest = board.length - 1;
colDest = board[0].length - 1;
solveState = new int[rowDest + 1][colDest + 1];
dpArray = new int[rowDest + 1][colDest + 1];
int ans = minMoveRecur(0,0, board);
if (ans == 100000000) {
return -1;
}
private static int minMoveRecur(int row, int col, int[][] board) {
if ((row == rowDest) && (col == colDest)) {
return 0;
}
if ((row < 0) || ( rowDest < row) || (col < 0) || (colDest < col)) {
return 100000000;
}
if (solveState[row][col] == 1) {
return dpArray[row][col];
}
solveState[row][col] = 1;
int up = row - board[row][col];
int down = row + board[row][col];
int right = col + board[row][col];
int left = col - board[row][col];
int vertBest = Math.min(minMoveRecur(up,col,board),minMoveRecur(down,col,board));
int horizBest = Math.min(minMoveRecur(row,right,board),minMoveRecur(row,left,board));
dpArray[row][col] = 1 + Math.min(vertBest,horizBest);
return dpArray[row][col];
}
我采用了一种递归关系，可以找到哪条路径导致了最小的跳数，但是对于我所拥有的其中一块测试板，我一直得到错误的答案
I take have a recursive relation that finds which path resulted in the minimum number of jumps, but I have been getting the wrong answer for one of test boards I have, where
int [][]board = {{2},{4},{2},{0},{4},{4},{3},{5},{1},{3}};
应该进行4次跳跃{(0,0)->(2,0)->(4,0)->(8,0)->(9,0)}，但我不断获得2次跳跃.我已经调试了几次，看来问题出在 vertBest 和 horizBest 上，而它们没有从递归调用中获取正确的值.似乎 vertBest 的值始终为0，一直到最后为1为止，然后将其从初始递归调用的 dpArray [row] [col]添加到1.= 1 + Math.min(vertBest，horizBest); 为2.它似乎并没有在其先前的调用中加上+1.
is supposed to take 4 jumps { (0,0) -> (2,0) -> (4,0) -> (8,0) -> (9,0) }, but I keep getting 2 jumps. I've debugged a few times, and it appears that the issue has to do with the vertBest and horizBest not getting the correct values from the recursive calls. It seems that vertBest's value is always 0, up until the very end where it is 1, which then is added to the 1 from the initial recursive call's dpArray[row][col] = 1 + Math.min(vertBest,horizBest); to be 2. It doesn't seem to be adding on the +1 from its earlier calls.
任何人都可以帮忙弄清楚这里出了什么问题吗?
Can anyone help shed some light on what's going wrong here?
推荐答案
当您尝试向上移动时，在 minMoveRecur(up，col，board)调用中， solveState [row][col] = 1 ，但是您尚未更新 dpArray [row] [col] .
When you try to go up, in the minMoveRecur(up,col,board) call, solveState[row][col] = 1 however you have not updated dpArray[row][col] yet.
由于 solveState [row] [col] = 1 和 dpArray [row] [col] 的结果，返回0(由于条件为3)并添加1.
As a result since solveState[row][col] = 1 and dpArray[row][col], 0 is returned (due to the 3rd if condition) and 1 is added to it.
这篇关于使用动态规划的矩阵的最小路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
