#62. Unique Paths

題目描述

將一個機器人放在m x n的表格中。機器人的開始位置在左上角(i.e., grid[0][0])。機器人嘗試移動到右下角(i.e., grid[m-1][n-1])。機器人在每單位時間只能選擇往下或往右移動。

給你兩個整數m和n，回傳機器人可以到達右下角的所有可能路徑，每個路徑都是唯一不重複的。

測試案例的結果被限制在少於等於2 * 10⁹。

限制條件

1 <= m, n <= 100

解題思路

Dynamic Programming

讓我們從最簡單的表格開始看。

Robot		Goal

Path : 1

Position:

(0,0) -> (0,1)

Robot

Goal

Path : 1

Position:

(0,0) -> (1,0)

在這兩個一維的表格中，機器人只會有一條路徑，也就是說，任何的一維路徑，結果都只會有一條路可走。

所以我們可以將表格標示如下：

Robot	1	Goal

Robot
1
Goal

讓我們將表格拓展成二維的表格。

Robot
	Goal

Path : 2

Position:

(0,0) -> (0,1) -> (1,1)
(0,0) -> (1,0) -> (1,1)

可以看到機器人就有兩條路徑可以走了，分別由橫向的一維路徑和縱向的一維路徑組成，所以我們可以表示成：

Robot	1
1	(2) Goal

繼續下去，我們先往右邊增加一欄。

Robot
		Goal

Path : 3

Position:

(0,0) -> (0,1) -> (0,2) -> (1,2)
(0,0) -> (0,1) -> (1,1) -> (1,2)
(0,0) -> (1,0) -> (1,1) -> (1,2)

路徑變成了3種，可以看到一維路徑仍然只有一條路，但是在(1,1)的位置則多出了一條新的路徑可以走，因此終點(1,2)就會有3條路徑可以到達。
而從(0,0)到(1,1)的路徑，我們將他單獨切分出來，剛好會是2*2表格的結果，我們將結果表示成：

Robot	1	1
1	(2) from [2*2]	(3) Goal

接著我們以2*2的表格往下拓展一列，看看結果。

Robot

	Goal

Path : 3

Position:

(0,0) -> (0,1) -> (1,1) -> (2,1)
(0,0) -> (1,0) -> (1,1) -> (2,1)
(0,0) -> (1,0) -> (2,0) -> (2,1)

路徑也是3種，同樣(0,0)到(1,1)的結果也是2*2表格的結果，所以表示成：

Robot	1
1	(2) from [2*2]
1	(3) Goal

從一維表格到二維表格再到拓展表格，可以看到一個規律，新的格子的路徑結果會等於前一個格子的路徑結果相加。
就像(1,1)有兩個結果，所以(1,2)或(2,1)的結果都會是2 + 1 = 3。

從這個規律往下推導，接著看3*3的表格。

Path : 6

Position:

(0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2)
(0,0) -> (0,1) -> (1,1) -> (1,2) -> (2,2)
(0,0) -> (0,1) -> (1,1) -> (2,1) -> (2,2)
(0,0) -> (1,0) -> (1,1) -> (1,2) -> (2,2)
(0,0) -> (1,0) -> (1,1) -> (2,1) -> (2,2)
(0,0) -> (1,0) -> (2,0) -> (2,1) -> (2,2)

Robot

		Goal

由於(1,2)或(2,1)的路徑數量都是3，因此(2,2)會等於它們兩個的結果相加也就是3+3=6。

Robot	1	1
1	2	3
1	3	Goal

public class Solution {
    public int UniquePaths(int m, int n) {
        var dp = new int[m,n];
        var visited = new HashSet<(int,int)>();
        var q = new Queue();        
        q.Enqueue((0,0));
        while(q.Count!=0){
            int len = q.Count;
            for(int i=0;i<q.Count;i++){
                (int x,int y) = (ValueTuple<int,int>) q.Dequeue();
                
				//For (0,0)
                if(x==0 && y==0) dp[x,y]=1;
				//For (0,i)
                else if(x==0) dp[x,y] = dp[x,y-1];
				//For (i,0)
                else if(y==0) dp[x,y] = dp[x-1,y];
				//
                else dp[x,y] = dp[x-1,y] + dp[x,y-1];                
                
                if(x+1<m && !visited.Contains((x+1,y))){
                     q.Enqueue((x+1,y));
                     visited.Add((x+1,y));
                }
                if(y+1<n && !visited.Contains((x,y+1))){
                     q.Enqueue((x,y+1));
                     visited.Add((x,y+1));
                }
            }
        }                
        return dp[m-1,n-1];
    }
}

複雜度分析：

時間複雜度：會一一計算每個格子，因此時間複雜度為O(m*n)。
空間複雜度：DP先建立了結果表格，因此空間複雜度為O(m*n)。

學習重點

Dynamic Programming