0064-minimum-path-sum.rb

# frozen_string_literal: true

# 64. Minimum Path Sum
# https://leetcode.com/problems/minimum-path-sum

=begin

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right, which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

### Example 1:
Input: grid = [[1,3,1],[1,5,1],[4,2,1]]
Output: 7
Explanation: Because the path 1 → 3 → 1 → 1 → 1 minimizes the sum.

### Example 2:
Input: grid = [[1,2,3],[4,5,6]]
Output: 12

### Constraints:
* m == grid.length
* n == grid[i].length
* 1 <= m, n <= 200
* 0 <= grid[i][j] <= 100

=end

# Runtime 72 ms
# Memory 212.3 MB
# @param {Integer[][]} grid
# @return {Integer}
defmin_path_sum(grid)
acc=[0] + [Float::INFINITY] * (grid[0].size - 1)

grid.each{ |row|
left=Float::INFINITY
acc.map!.with_index{ |n,i| left=row[i] + (left < n ? left : n)}
}

acc.last
end

# ********************#
# TEST #
# ********************#

require"test/unit"
classTest_min_path_sum < Test::Unit::TestCase
deftest_
assert_equal7,min_path_sum([[1,3,1],[1,5,1],[4,2,1]])
# assert_equal 12, min_path_sum([[1,2,3],[4,5,6]])
end
end