【leetcode62】 62. Unique Paths解题

• 关键字：动态规划、递归
• 难度：Medium
• 题目大意：计算两网格之间所有可能路径，只能向右或下行走

题目：

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?

robot_maze.png

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

Note: m and n will be at most 100.
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

思路：

1、暴力递归：leetcode超时了；
2、动态规划：定义p(i, j)为 从开始位置到坐标(i，j)的所有可能路径，则：

• i==1或j==1时，显然p(i, j) = 1;
• 其他情况下，p(i , j) = p(i-1, j) + p(i, j-1);
  以m=7，n=3为例，dp数组可以正序填充：

DP填充.jpeg

代码实现：

解法1：

public class solution {
    public  int uniquePaths(int m, int n) {
        return process(n,m);
    }

    private  int process(int i, int j) {
        if(i==1||j==1) return 1;
        return process(i-1,j) + process(i,j-1);
    }
}

解法2：

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