81_sol.rb

# **PROBLEM STATEMENT**
#Given an mxn matrix A of non-negative integers,
# find the finite sequence S of adjacent entries of
# A (starting from top left and moving right, or bottom)
# s.t Σ(S) is minimum.

# **OPTIMAL SUBSTRUCTURE**
# Claim: If S is the opt. solution for A, then S' = S[:-1] is optimal to
# the subproblem with force S[-1].

# Proof: Omitted, since similar to previous problems.

# **OVERLAPPING SUBPROBLEMS**
# Any S[i+p][j+k] for some fixed i,j and p,k ranging in rows, columns of A
#respectively will recompute S[i][j].

# **RECURRENCE RELATION**
# S[0][0] = A[0][0]
# S[i][j] = min{ S[i-1][j] , S[i][j-1] } + A[i][j]

A =
[
    [131, 673, 234, 103, 18],
    [201, 96, 342, 965, 150],
    [630, 803, 746, 422, 111],
    [537, 699, 497, 121, 956],
    [805, 732, 524, 37, 331]
]

def min_path_sum_dp a
  rows = a.length
  cols = a[0].length
  s = Array.new(rows) {Array.new(cols) {0}}

  for i in 0..(rows-1)
    for j in 0..(cols-1)
      if i == 0 and j == 0
        s[0][0] = a[0][0]
        next
      elsif i == 0
        s[i][j] = s[i][j-1] + a[i][j]
      elsif j == 0
        s[i][j] = s[i-1][j] + a[i][j]
      else
        s[i][j] = [ s[i-1][j], s[i][j-1] ].min + a[i][j]
      end
    end
  end

  return s[rows-1][cols-1]
end

puts min_path_sum_dp A