62.UniquePaths

  • Z时代
  • 2024-01-10
  • 分类：综合

编程

题目：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();
    }
}

 

以上是 62.UniquePaths 的全部内容， 来源链接： utcz.com/z/518187.html

回到顶部