[LeetCode] 62. Unique Paths

轉自LeetCode

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?

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

Note: m and n will be at most 100.

<Solution>

這題用 recursive，也就是用 DFS 的做法也可以，但是會 TLE

所以需要換種思路，可以用 dynamic programming 來處理

首先，因為只能往右或往下，所以 row 0 和 col 0 都只有一條路可走

因此 dp[0][0..n-1] 都等於 0，dp[0..m-1][0] 都等於 0

那其他的格子，可以從左方走過來，或是上方走過來

因此 dp[i][j] = dp[i-1][j] + dp[i][j-1]，1 <= i < m, 1 <= j < n

可以就用這個公式去解

那這邊還有一個地方可以用來節省空間

從推導出來的數學式來看，意義就是從上方來的方式，加上從左方來的方式

那麼，其實不用使用到二維陣列，用一維陣列 dp[n] 來算就好

一開始的初始值，就都是 1，因為 row 0 就只有一種方式可以走

然後計算 row 1 的時候，dp[n] 已經是 row 0 的結果了，代表從上方來的方式已經加完了

這時候再計算從左方來的方式就可以了

code 如下
c++

	class Solution {
	public:
	int uniquePaths(int m, int n) {
	if(m == 1 && n == 1) {
	return 1;
	}
	//> dynamic programming
	vector<int> dp(n, 1);
	for(int r = 1; r < m; r++) {
	for(int c = 1; c < n; c++) {
	dp[c] += dp[c-1];
	}
	}
	return dp[n-1];
	}
	};

view raw findUniquePaths_1.cpp hosted with ❤ by GitHub

kotlin

	class Solution {
	fun uniquePaths(m: Int, n: Int): Int {
	var dp = Array(m) { IntArray(n) {1} }
	var r = 1
	var c = 1
	for(r in 1 until m) {
	for (c in 1 until n) {
	dp[r][c] = dp[r-1][c] + dp[r][c-1]
	}
	}
	return dp[m-1][n-1]
	}
	}

view raw unique_paths.kt hosted with ❤ by GitHub

那這題還有一種很數學的解法

因為只能往下和往右走，所以其實就是往下走 m-1 步，往右走 n-1 步，總共走 m + n - 2 步

那怎麼走，會受限於 m 和 n 比較小的那個數，假設 m > n

那麼，當走了 n-1 步往右之後，之後剩往下走這 1 個方式

用數學式來看，就是從 m + n - 2 個步數中，選出 m-1 和 n-1 當中比較小的那個

code 如下

	class Solution {
	public:
	int uniquePaths(int m, int n) {
	if(m == 1 && n == 1) {
	return 1;
	}
	//> use double to avoid overflow
	double numerator = 1.0, denominator = 1.0;
	int total = m + n - 2;
	int choice = (m > n) ? n - 1 : m - 1;
	for(int i = 1; i <= choice; i++) {
	numerator *= (total - i + 1);
	denominator *= i;
	}
	return static_cast<int>(numerator/denominator);
	}
	};

view raw findUniquePaths_2.cpp hosted with ❤ by GitHub