62. Unique Paths

原创
07/10 00:03
阅读数 35

题目:62. 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 7 x 3 grid. How many possible unique paths are there?

Example 1:

Input: m = 3, n = 2
Output: 3
Explanation:
From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Right -> Down
2. Right -> Down -> Right
3. Down -> Right -> Right

Example 2:

Input: m = 7, n = 3
Output: 28

Constraints:

  • 1 <= m, n <= 100
  • It's guaranteed that the answer will be less than or equal to 2 * 10 ^ 9.

解题思路

设h(i, j)为从(i, j)坐标出发到达右下角的可行路径数,则h(0, 0)为题目所求。因为机器人只能够向右或者向下移动,所以可以发现,h(0, 0)的值取决于h(0, 1)和h(1, 0),h(0, 0) = h(0, 1) + h(1, 0)。以此类推,对于任何一个位置,它到右下角的可行路径数,都只取决于它的右边一格和下方一格到右下角的可行路径数,即有h(i, j) = h(i+1, j) + h(i, j+1)。因此,我们可以写出下面的动态规划地推公式:

动态规划的递推公式:

h(i,j) = h(i+1,j) + h(i,j+1) // 当i+1<=m-1,或j+1<=n-1时
h(i,j) = 0 // 当i+1>m-1(表示已经处于最右边的那一列格子),或j+1>n-1(表示已经处于最下面的那一行格子)时
h(m-1,n-1) = 1  // 表示右下角的格子

接下来按照上述递推公式求出h(0,0)即可。

时间复杂度分析

从最右下角开始考虑,最右下角的位置是h(m-1, n-1),那么右下角往上一个格子h(m-2, n-1)=h(m-1, n-1)+h(m-2, n),因为h(m-2, n)已经超出范围,所以h(m-2, n)=0,只需要考虑h(m-1, n-1),这一步就相当于在计算h(m-1, n-1)的基础上增加O(1)的时间复杂度。同样地,h(m-1, n-2)也是在h(m-1, n-1)的基础上增加O(1)的时间复杂度。更进一步地,h(m-2, n-2)=h(m-2, n-1)+h(m-1, n-2),由于h(m-2, n-1)和h(m-1, n-2)已经被算过一次,所以无须再作计算,所以h(m-2, n-2)是在h(m-2, n-1)和h(m-1, n-2)的基础上增加O(1)的时间复杂度。由此可见,h(i, j)是在h(i+1,j) 和 h(i,j+1)的基础上增加O(1)的时间复杂度,而h(i, j)首次计算出来之后可以保存起来,这样一来就没有了重复计算的过程,最终的时间复杂度取决于格子的总个数,即为O(mn)。

最终实现

Java 实现

import java.util.Scanner;

public class Solution {

    private int h[][];

    public int uniquePaths(int m, int n) {
        // initialize the two-dimension array h
        h = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                h[i][j] = -1;
            }
        }
        // set the right-bottom position to 1
        h[m-1][n-1] = 1;
        return calcH(0, 0);
    }

    private int calcH(int i, int j) {
        int m = h.length;
        int n = h[0].length;
        if (i >= m || j >= n) {
            return 0;
        }
        if (h[i][j] != -1) {
            return h[i][j];
        }
        h[i][j] = calcH(i + 1, j) + calcH(i, j + 1);
        return h[i][j];
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        Scanner scanner = new Scanner(System.in);
        while(true) {
            int m = scanner.nextInt();
            int n = scanner.nextInt();
            if (m == -1 || n == -1) {
                break;
            }
            int res = solution.uniquePaths(m, n);
            System.out.println(res);
        }
        scanner.close();
    }

}

 

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
在线直播报名
返回顶部
顶部