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
Top comments (1)
I appreciate seeing the brute force approach first.
If you continue this series, I would be interested to see the LeetCode ranking for speed and memory next to the code 😁