題目連結: https://leetcode.com/problems/unique-paths/
法ㄧ(Iterative version):
func uniquePaths(_ m: Int, _ n: Int) -> Int {
var matrix = Array(repeating: Array(repeating: 0, count: n), count: m)
for i in 0 ..< m {
for j in 0 ..< n {
if i == 0 || j == 0 {
matrix[i][j] = 1
} else {
matrix[i][j] = matrix[i-1][j] + matrix[i][j-1]
}
}
}
return matrix[m-1][n-1]
}
法二(Recursive version):
(p.s. Correctness but Time Limit Exceeded)
func uniquePaths(_ m: Int, _ n: Int) -> Int {
return helper(0, 0, n - 1, m - 1)
}
func helper(_ curX: Int, _ curY: Int, _ targetX: Int, _ targetY: Int) -> Int {
if curX == targetX && curY == targetY {
return 1
}
var down = 0
var right = 0
if curX < targetX {
down = helper(curX + 1, curY, targetX, targetY)
}
if curY < targetY {
right = helper(curX, curY + 1, targetX, targetY)
}
return down + right
}