題目描述

一個機器人位于一個 m x n 網(wǎng)格的左上角 （起始點在下圖中標記為“Start” ）。

機器人每次只能向下或者向右移動一步。機器人試圖達到網(wǎng)格的右下角（在下圖中標記為“Finish”）。

問總共有多少條不同的路徑？

圖表

示例 1:

輸入: m = 3, n = 2
輸出: 3
解釋:
從左上角開始，總共有 3 條路徑可以到達右下角。
1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右

示例 2:

輸入: m = 7, n = 3
輸出: 28

提示：
1 <= m, n <= 100
題目數(shù)據(jù)保證答案小于等于 2 * 10 ^ 9

思路分析

動態(tài)規(guī)劃三步：

• 第一步找到dp數(shù)組的定義，我們可以定義dp[i][j]表示從(0,0)坐標點出發(fā)到達坐標點(i,j)的所有路徑，對于m行n列的所有路徑就是dp[m-1][n-1]的值；
• 第二步是找到數(shù)組元素之間的關系。首先考慮第一行和第一列的情況，因為只能向下和向右，第一行只能一直向右走，第一列只能向下走(不能向左或向上)，所以dp[0][i]和dp[j][0]的值為1；針對于中間的坐標點(i,j),i>0,j>0有兩個方向可以到達，一個方向是(i-1,j),一個方向是(i,j-1)，分別從它上邊和左邊，所以我們可以得到關系：dp[i][j]=dp[i-1][j]+dp[i][j-1],i>0,j>0；
• 第三步找到初始值，在第二步的時候我們已經(jīng)知道了第一行和第一列的值為1；

代碼實現(xiàn)

public class Solution62 {
    public int uniquePaths(int m, int n) {
        //`dp[i][j]`表示從`(0,0)`坐標點出發(fā)到達坐標點`(i,j)`的所有路徑
        int[][] dp = new int[m][n];
        ///第一行
        for (int i = 0; i < n; i++) {
            dp[0][i] = 1;
        }
        ///第一列
        for (int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }
        ///中間部分
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m - 1][n - 1];
    }

    public static void main(String[] args) {
        Solution62 solution62 = new Solution62();
        System.out.println("res:" + solution62.uniquePaths(3, 2));
        System.out.println("res:" + solution62.uniquePaths(7, 3));
    }
}

歡迎關注南閣公眾號

南閣子也