Leetcode #62. Unique Paths

有一個機器人，它只能往右跟往下走，找出可到達終點，而且不重複的走法次數。
ex: m=2 n=3

看圖用肉眼數一下就知道了吧
總共有3個走法 (記得只能往右跟往下走哦)
但如果你把m、n的數值拉大，你就沒辦法用眼睛算了～

那怎麼辦呢，大家可以先努力想一下!!

• 註: 1 < m,n < 100

防雷
防雷
防雷

第一次看到這題目，我暴力解都沒辦法XD，後來跑去看解法，想了很久才懂(煙
像這種的題目都會歸類叫Dynamic Programming(動態規劃)
我們需要去找出關係，轉化為一個公式，才有辦法解出題目（所以有可能永遠想不出來XD，看答案不可恥

行跟列拉大一點，把每一個位置的走法可能性，自己先算一下，就會得出下圖。

有沒有發現每一個數值的關係，因為機器人只能往右跟往下，所以行跟列只有一個走法
而其他的位置就是左邊那格+上面那格，終點6可以透過左邊的3，跟上面的3相加出來

以公式來說就是:
dp[m][n] = dp[m-1][n] + d[m][n-1]

程式:

func uniquePaths(m int, n int) int {
	dp := [100][100]int{}
	// 每列的第一個位置都是1
	for column := 0; column < m; column++ {
		dp[column][0] = 1
	}
	// 第一行都是1
	for row := 0; row < n; row++ {
		dp[0][row] = 1
	}

	for column := 1; column < m; column++ {
		for row := 1; row < n; row++ {
			dp[column][row] = dp[column-1][row] + dp[column][row-1]
		}
	}

	return dp[m-1][n-1]
}

最後的資料結構來講樹～
Bye!