了解动态编程

我刚开始学习DP和试图解决使用相同的（https://leetcode.com/problems/unique-paths/）了解动态编程

机器人位于amxn格的左上角从本文给出了这个问题（注明“开始'在下图中）。

机器人只能在任何时间点向下或向右移动。机器人正在尝试到达网格的右下角（在下图中标记为“完成”）。

有多少种可能的独特路径？

这里是我的尝试：

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

很抱歉，如果这听起来很基本的，我知道我失去了一些东西。任何人都可以指出它有什么问题吗？

来源

2016-03-15 user3738248

可能的[在NxN网格中查找所有路径的算法]的副本（http://stackoverflow.com/questions/9105699/algorithm-for-finding-all-paths-in-a-nxn-grid） – Aaron

为了解决这个问题，我们定义一个循环公式为f(r,c)。可能有几个选项可以做到，但让我们坚持你的代码。

f(r, c) = 0 if r >= m
f(r, c) = 0 if c >= n
f(r, c) = 1 if 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）存在于胰岛β细胞（M-1，N-1）β细胞？

来源

2016-03-15 20:58:45

了解动态编程

回答

相关问题