[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++

kotlin

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

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

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

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

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

code 如下