Day.22 Unique Paths

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!