Pythonの最小経路合計

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

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

手順を見てみましょう-

• a：=行数、b：=列数
• i：=a – 1、j：=b – 1
• while j> =0
  • matrix [a、j]：=matrix [a、j] + matrix [a、j + 1]
  • jを1つ減らします
• while i> =0
  • matrix [i、b]：=matrix [i、b] + matrix [i + 1、b]
  • iを1つ減らします
• j：=b – 1およびi：=行– 1
• while i> =0
  • while j> =0
    • matrix [i、j]：=matrix [i、j] + matrix [i、j+1]とmatrix[i+ 1、j]の最小値
    • jを1つ減らします
  • j：=b – 1
  • i：=i – 1
• return matrix [0、0]

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

例

class Solution(object):
   def minPathSum(self, grid):
      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])
ob1 = Solution()
print(ob1.minPathSum([[1,3,1],[1,5,1],[4,2,1]]))

入力

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

出力

7