C++での最小パス合計

非負の整数で満たされたmxn行列があると仮定し、そのパスに沿ったすべての数値の合計を最小化する左上隅から右下隅へのパスを見つけます。動きは、どの時点でも下または右のいずれかになります。たとえば、マトリックスが次のような場合

出力は7になり、パスは1,3,1,1,1になります。これにより、合計が最小化されます

手順を見てみましょう-

• a：=行数、b：=列数

• i：=a – 1、j：=b-1

• 一方、j> =0

  • matrix [a、j]：=matrix [a、j] + matrix [a、j + 1]

  • jを1減らします

• i> =0

  • matrix [i、b]：=matrix [i、b] + matrix [i + 1、b]

  • iを1減らします

• j：=b-1およびi：=行-1

• i> =0

  • 一方、j> =0

    • matrix [i、j]：=matrix [i、j]+最小のmatrix[i、j+1]およびmatrix[i+ 1、j]

    • jを1減らします

  • j：=b-1

  • i：=i-1

• 行列を返す[0、0]

例

理解を深めるために、次の実装を見てみましょう-

class Solution(object):
   def minPathSum(self, grid):
      """
      :type grid: List[List[int]]
      :rtype: int
      """
      row = len(grid)-1
      column = len(grid[0])-1
      i=row-1
      j=column-1
      while j>=0:
         grid[row][j]+=grid[row][j+1]
         j-=1
      while i>=0:
         grid[i][column]+=grid[i+1][column]
         i-=1
      j=column-1
      i = row-1
      while i>=0:
         while j>=0:
         grid[i][j] += min(grid[i][j+1],grid[i+1][j])
         j-=1
      j=column-1
      i-=1
   return(grid[0][0])

入力

[[1,3,1],[1,5,1],[4,2,1]]

出力

7