LeetCode64. 最小パスと(Python)
非負の整数を含むmxnメッシュを指定します.左上から右下に向かうパスを見つけて、パスの数値の合計が最小になります.
説明:毎回1歩下または右に移動するしかありません.
例:
コードの考え方:
動的計画の方法を採用する.まず境界での歩数を算出し,次に考えられるものと考えられるものの中で最も短いものを選択する.
コード実装:
class Solution(object): def pathMinSum(self, nums): row_count = len(nums) col_count=len(nums[0])#列境界を歩く歩数for i in range(1,row_count):nums[i][0]+=nums[i-1][0]#行境界を歩く歩数for j in range(1,col_count):nums[0][j]+=nums[0][j-1]#歩数が最も短いfor i in rangeを選択(1, row_count): for j in range(1, col_count): nums[i][j] += min(nums[i-1][j],nums[i][j-1])
return nums[-1][-1]
説明:毎回1歩下または右に移動するしかありません.
例:
:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
: 7
: 1→3→1→1→1 。コードの考え方:
動的計画の方法を採用する.まず境界での歩数を算出し,次に考えられるものと考えられるものの中で最も短いものを選択する.
コード実装:
class Solution(object): def pathMinSum(self, nums): row_count = len(nums) col_count=len(nums[0])#列境界を歩く歩数for i in range(1,row_count):nums[i][0]+=nums[i-1][0]#行境界を歩く歩数for j in range(1,col_count):nums[0][j]+=nums[0][j-1]#歩数が最も短いfor i in rangeを選択(1, row_count): for j in range(1, col_count): nums[i][j] += min(nums[i-1][j],nums[i][j-1])
return nums[-1][-1]