题目描述
blablabla
样例
class Solution:
def findMinCost(self, matrix):
n = len(matrix)
m = len(matrix[0])
dp = [[float('inf')] * m for _ in range(n)]
dp[0][0] = matrix[0][0]
for i in range(n):
for j in range(m):
if i > 0:
dp[i][j] = min(dp[i][j], dp[i - 1][j] + matrix[i][j])
if j > 0:
dp[i][j] = min(dp[i][j], dp[i][j - 1] + matrix[i][j])
return dp[n - 1][m - 1]
if name == ‘main’:
n = int(input())
matrix = []
for i in range(n):
matrix.append(list(map(int, input().split())))
s = Solution()
print(s.findMinCost(matrix))
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla