LeetCode in Ruby: 62. Unique Paths

#leetcode #ruby #dynamicprogramming

Backtracking

def unique_paths(m, n)
  backtrack(0, 0, m, n)
end

def backtrack(r, c, m, n)
  if r == m - 1 && c == n - 1
    return 1
  end
  if r >= m || c >= n
    return 0
  end
  backtrack(r + 1, c, m, n) + backtrack(r, c + 1, m, n)
end

This is a brute force approach to solve the problem. Don't submit this solution on LeetCode because it will exceed the time limit. It traverses all the possible paths by using a technique called backtracking.

Memorization (Top-Down)

def unique_paths(m, n)
  @cache = Array.new(m + 1) { Array.new(n + 1, -1) }
  backtrack(0, 0, m, n)
end

def backtrack(r, c, m, n)
  return 1 if r == m - 1 && c == n - 1
  return 0 if r >= m || c >= n

  @cache[r + 1][c] = backtrack(r + 1, c, m, n) if @cache[r + 1][c] == -1
  @cache[r][c + 1] = backtrack(r, c + 1, m, n) if @cache[r][c + 1] == -1
  @cache[r + 1][c] + @cache[r][c + 1]
end

Memorization (Bottom-Up)

def unique_paths(m, n)
  @cache = Array.new(m + 1) { Array.new(n + 1, 0) }
  @cache[m - 1][n] = 1
  (m - 1).downto(0).each do |r|
    (n - 1).downto(0).each do |c|
      @cache[r][c] = @cache[r + 1][c] + @cache[r][c + 1]
    end
  end
  @cache[0][0]
end