題目連結: https://leetcode.com/problems/unique-paths/

參考解法: https://leetcode.com/problems/unique-paths/discuss/1912575/100-Fastest-Swift-Solution-time%3A-O(n-*-m)-space%3A-O(min(n-m)).

法ㄧ(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
}