一個機器人位于一個 m x n 網格的左上角 （起始點在下圖中標記為 “Start” ）。
機器人每次只能向下或者向右移動一步递雀。機器人試圖達到網格的右下角（在下圖中標記為 “Finish” ）柄延。問總共有多少條不同的路徑？
exp1
例如
輸入：m = 3, n = 7
輸出：28
輸入：m = 3, n = 2
輸出：3
方法1: 動態(tài)規(guī)劃
動態(tài)規(guī)劃其實是比較好理解, 也是相對來說比較好處理此問題方法
舉個栗子: 比如要走到 (i, j) 格子, 因為機器人只可以向下或者向右,
固他只能從上方(i - 1, j)下來 或者左方(i, j - 1)向右走過來
我們再看幾張圖
exp2
(上邊界, 左邊界只有 1種路線, 因為機器人只能右或下移動)
exp3
exp4
exp5
我們可以直觀看到, 如果我們用f(i, j)表示從左上角走到(i, j)的路徑數量, 那么可得到動態(tài)規(guī)劃的方程式:
f(i, j) = f(i - 1, j) + f(i, j - 1)
func uniquePaths(_ m: Int, _ n: Int) -> Int {
var dp = [[Int]](repeating: [Int](repeating: 0, count: n), count: m)
for i in 0..<m {
dp[i][0] = 1
}
for j in 0..<n {
dp[0][j] = 1
}
for i in 1..<m {
for j in 1..<n {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
}
}
return dp[m-1][n-1];
}
其實為了方便些, 我們可以初始建立全為1的dp數組, 固優(yōu)化上面代碼可得
func uniquePaths(_ m: Int, _ n: Int) -> Int {
var dp = [[Int]](repeating: [Int](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[m-1][n-1];
}
方法2: 數學公式
這道題比較好的地方是從左上角到右下角, 固針對 m x n 網格, 需要移動 m + n - 2次, 其中 m - 1 次向下移動, n - 1 次向右移動缀程。固從 m + n - 2次移動中選擇 m - 1次向下移動方案數, 即
formula
(m!表示 m 的階乘, 例如 3!=3X2X1, 5!=5X4X3X2X1)
func uniquePaths(_ m: Int, _ n: Int) -> Int {
var ans = 1, x = n, y = 1
while y < m {
ans = ans * x / y
x += 1
y += 1
}
return ans;
}
題目來源：力扣（LeetCode） 感謝力扣爸爸 :)
IOS 算法合集地址
