# Ruby Solution - DP

• The DP formula is `dp[i][j] = dp[i-1][j] + dp[i][j-1]`. We can only record the `last_row[]` to save some space.

``````require 'minitest/autorun'

class FooTest < Minitest::Test
# Using DP
def unique_paths_with_obstacles(obstacle_grid)
last_row = []
obstacle_grid[0].each_with_index do |ele, i|
if i == 0
last_row << (1^ele)
else
if ele == 1
last_row[i] = 0
else
last_row[i] = last_row[i-1]
end
end
end

obstacle_grid[1..-1].each_with_index do |row, i|
last_row[0] = row[0] == 1 ? 0 : last_row[0]

row[1..-1].each_with_index do |ele, j|
if ele == 1
last_row[j+1] = 0
else
last_row[j+1] += last_row[j]
end
end
end

last_row[-1]
end

def test_run
ar = [ [1] ]
assert_equal 0, unique_paths_with_obstacles(ar)

ar = [ [0] ]
assert_equal 1, unique_paths_with_obstacles(ar)

ar = [ [0,1] ]
assert_equal 0, unique_paths_with_obstacles(ar)

ar = [ [1,0] ]
assert_equal 0, unique_paths_with_obstacles(ar)

ar = [ [1,0],[0,0] ]
assert_equal 0, unique_paths_with_obstacles(ar)

ar = [
[0,0,0],
[0,1,0],
[0,0,0]
]
assert_equal 2, unique_paths_with_obstacles(ar)

ar = [
[0,0,0,0,0],
[0,0,0,0,0],
[0,0,1,0,0],
[0,0,0,1,0],
[0,0,0,0,0],
]
assert_equal 18, unique_paths_with_obstacles(ar)
end
end
``````

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