不同的路径

题目

有一个机器人的位于一个 m × n 个网格左上角。机器人每一时刻只能向下或者向右移动一步。机器人试图达到网格的右下角。问有多少条不同的路径?
http://www.lintcode.com/zh-cn/problem/unique-paths/

分析

由于机器人只能向右或者向下移动,因此:当机器人处在最后一行的任意一列网格上,其下一步永远只能向右移动;同理,当机器人处在最后一列时,其下一步永远只能向下移动。

而对于任何既不在最后一行、也不在最后一列的坐标,机器人可以走的路径数,就是其向下一步的可行路径数与其向右一步的可行路径数之和。如果我们知道了其向右、向下一步的可行路径数,就知道了当前坐标的可行路径数。而当我们重复这个步骤时,终归会走到最右或者最下的路径上,而那一刻的可行路径数是已知的。

因此,这题可以使用动态规划来做。使用一个二维数组helper来记录从某个点出发抵达右下角的可行路径数。显然,helper的最后一行和最后一列的值均为1,而两者交叉点helper[m-1][n-1]可记为0,因为那就是终点。

对于任何helper未知的坐标,就递归调用以求终点至该坐标右边、下边的可行路径数,对两者求和,就知道了当前坐标的可行路径数,此时可以更新helper,以加快后续坐标的计算速速。

代码


public class Solution {
    
    int steps(int row, int col, int[][] helper){
        if(helper[row][col] != -1){
            return helper[row][col];
        }
        
        if(row != helper.length - 1){
            if(col != helper[row].length - 1){
                int down = steps(row+1, col, helper);
                int right = steps(row, col+1, helper);
                helper[row][col] = down + right;
                return helper[row][col];
            }else{
                helper[row][col] = 1;
                return helper[row][col];
            }
        }else{
            helper[row][col] = 1;
            return helper[row][col];
        }
    }
    /*
     * @param m: positive integer (1 <= m <= 100)
     * @param n: positive integer (1 <= n <= 100)
     * @return: An integer
     */
    public int uniquePaths(int m, int n) {
        // write your code here
        int[][] helper = new int[m][n];
        for(int i=0; i < m; i++){
            for(int j=0; j < n; j++){
                helper[i][j] = -1;
            }
        }
        helper[m-1][n-1] = 0;
        return steps(0, 0, helper);
        
    }
}
Show Comments

Get the latest posts delivered right to your inbox.