leetcode: Unique Paths

问题描述：

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

How many possible unique paths are there?

Above is a 3 x 7 grid. How many possible unique paths are there?

Note: m and n will be at most 100.

原问题链接：https://leetcode.com/problems/unique-paths/

 

问题分析

    这个问题比较有意思，因为它从一开始看机器人的移动位置的时候，有点不太好找到思路。要解决这个问题，需要充分利用问题里提到的一个限制条件，就是机器人每次只能考虑向左或者向下移动。这样，我们要求它所有可能的移动路径时，就需要结合这个条件进行计算推导。

　　我们可以首先从最简单的形式来考虑，对于1 x 1的矩阵来说，它的起始节点和终止节点就是在一个点上，可以认为是１。而对于2 x 2的矩阵来说呢，对于节点[0][1]来说，它只能有一种选择，也就是说它到终点的路径数是１，对于[1][0]来说也一样。而对于[0][0]来说，它可以向下也可以向右移动，所以它的路径的数量等于它左边节点和它下面节点的路径数的和。也就是path(i, j) = path(i + 1, j) + path(i, j + 1);　所以我们就得到了路径数计算的推导关系。

　　另外，具体看矩阵，它的最后一行和最后一列所有的点其实就只有一种路径。这些可以作为初始条件。然后我们可以根据前面的path推导条件循环往前递推。这过程有点像动态规划的思路。我们从matrix[i - 2][j - 2]开始，每次一行或者一列的去计算当前位置的值，直到最后的matrix[0][0]。

　　这样，我们可以得到如下的代码实现：

 

public class Solution {
    public int uniquePaths(int m, int n) {
        if(m <= 1 || n <= 1) return 1;
        int[][] matrix = new int[m][n];
        for(int i = 0; i < n; i++) matrix[m - 1][i] = 1;
        for(int i = 0; i < m; i++) matrix[i][n - 1] = 1;
        for(int i = m - 2; i >= 0; i--) {
            for(int j = n - 2; j >= 0; j--)
                matrix[i][j] = matrix[i + 1][j] + matrix[i][j + 1];
        }
        return matrix[0][0];
    }
}