我刚刚开始学习 dp 并尝试使用相同的(https://leetcode.com/problems/unique-paths/)从 leetcode 解决这个问题
机器人位于 m x n 网格的左上角(在下图中标记为“开始”)。
机器人只能在任何时间点向下或向右移动。机器人正试图到达网格的右下角(在下图中标记为“完成”)。
有多少条可能的唯一路径?
这是我尝试过的:
public class Solution {
public int uniquePaths(int m, int n) {
int [][] grid = new int[m][n];
int [][] memo = new int[m][n];
return uniquePathsHelper(grid,m,n,memo);
}
public int uniquePathsHelper(int [][] grid, int row,int col,int[][]memo){
if(row>grid.length-1 || col>grid[0].length-1) return -1;
if(row == grid.length-1 && col == grid[0].length-1) return 0;
if(memo[row][col]!=0) return memo[row][col];
if(col == grid[0].length-1) memo[row][col] = uniquePathsHelper(grid,row+1,col,memo)+1;
if(row == grid.length-1) memo[row][col] = uniquePathsHelper(grid,row,col+1,memo)+1;
// int rowInc = Integer.MIN_VALUE;
// int colInc = Integer.MIN_VALUE;
// if(row<grid.length-1) rowInc = uniquePathsHelper(grid, row+1,col,memo);
// if(col<grid.length-1) colInc = uniquePathsHelper(grid,row,col+1,memo);
// if(row == grid.length-1 || col == grid[0].length-1) return 1;
// if(row<grid.length-1) return 2;
// if(col<grid[0].length-1) return 2;
if(col< grid[0].length-1 && row < grid.length-1) memo[row][col] = memo[row+1][col] + memo[row][col+1];
System.out.println("Memo["+row+"]["+col+"] = "+memo[row][col]);
return memo[0][0];
}
}
抱歉,如果这听起来很基础,我知道我遗漏了一些东西。任何人都可以指出它有什么问题吗?
最佳答案
为了解决这个问题,让我们为 f(r,c)
定义一个递归公式。可能有多种选择,但让我们坚持使用代码中的内容。
f(r, c) = 0 如果 r >= m
f(r, c) = 0 如果 c >= n
f(r, c) = 1 如果 r == m && c == n
f(r, c) = f(r + 1, c) + f(r, c + 1)
根据公式,uniquePathsHelper
会是什么样子?
// actually we don't need grid at all.
// assume that we have m rows and n cols, m and n are global variables
public int uniquePathsHelper(int row, int col, int[][] memo) {
// 1-st and 2-d formulas
if(row >= m || col >= n) return 0;
// 3-d formula
if(row == m - 1 && col == n - 1) return 1;
if(memo[row][col] != 0) {
// 4-th formula
memo[row][col] = uniquePathsHelper(row, col + 1, memo) +
uniquePathsHelper(row + 1, col, memo);
}
return memo[row][col];
}
要获得答案,只需调用 uniquePathsHelper(0, 0, memo)
,这意味着 从 (0,0)-cell 到 (m-1, n-1)-细胞?
关于java - 通过一个例子理解动态规划,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/36020726/