Ruby Solution - DP


  • 0
    I

    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
    

Log in to reply
 

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