Dynamic Programming with Memorization in Swift


  • 0
    U

    This is typical DP problem. Because the robot can only move 2 directions, which means the total number of unique paths up(m,n) = up(m-1) + up(n-1). Finally, we need to use memorization to reduce repeatitive calculation.

    func uniquePaths(_ m: Int, _ n: Int) -> Int {
      var memo = [String: Int]()
      return search(m, n, &memo)
    }
    
    func search(_ m: Int, _ n: Int, _ memo: inout [String: Int]) -> Int {
      if m == 1 || n == 1 { return 1 }
      let key = String(m) + "-" + String(n)
      if let c = memo[key] { return c }
      let count = search(m-1, n, &memo) + search(m, n-1, &memo)
      memo[key] = count
      return count
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.