題目
給一個 m x n 的棋盤,從左上角的格子出發,規定只能往右走跟往下走,問要到達右下角的格子可以有幾種路徑
Example:
Input: m = 3, n = 3
Output:
6
思路
找出 dp 方程式,例如這題,因為規定只能往右跟往下走,
每一格的結果是由:上面的格子 + 左邊的格子 的結果 (如下圖)
dp 方程式為: dp[i][j] = dp[i-1][j] + dp[i][j-1]
以下列出 3 x 3 所有 6 種路徑
程式碼
▼ Swift 可以用 Array 的 set default value 的 function,做出 2D array,即 array of array
class Solution {
func uniquePaths(_ m: Int, _ n: Int) -> Int {
if m == 0 || n == 0{
return 0
}
var dp = Array(repeating:Array(repeating:1,count:n), count:m)
for i in 1..<m {
for j in 1..<n {
dp[i][j] = dp[i-1][j] + dp[i][j-1]
}
}
return dp.last?.last ?? 0
}
}
▼ 至於為什麼 default 值要給 1 呢?
因為當 dp[i][0] 跟 dp[0][j] 都是一種路徑,所以預設給 1,而其他格子也給 1 是因為方便偷懶XD 更好的寫法也許是操縱 dp[i][0] 跟 dp[0][j] 給值 1 就好
▼ 填上每一格的路徑數
時間複雜度: O(m x n)
空間複雜度: O(m x n)