矩阵的最小路径和

class Solution:
    def minPathSum(self , matrix: List[List[int]]) -> int:
        # 定义a[i][j]为走到当前单元格时的最小路径和
        # 那么状态转移矩阵为a[i][j] = min(a[i-1][j], a[i][j-1]) + matrix[i][j]
        # 输出结果为a[m-1][n-1]
        # 边界条件为：a[i][0] = a[i-1][0] + matrix[i][0]; a[0][j] = a[0][j-1] + matrix[0][j-1]
        m, n = len(matrix), len(matrix[0])
        a = [[matrix[0][0] for _ in range(n)] for _ in range(m)]

        for i in range(1,m):
            a[i][0] = a[i-1][0] + matrix[i][0]
        for j in range(1,n):
            a[0][j] = a[0][j-1] + matrix[0][j]
        for i in range(1, m):
            for j in range(1, n):
                a[i][j] = min(a[i-1][j], a[i][j-1]) + matrix[i][j]
        return a[m-1][n-1]

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param matrix int整型二维数组 the matrix
# @return int整型
#
class Solution:
    def minPathSum(self , matrix: List[List[int]]) -> int:
        ret = [i for i in matrix[0]]
        acc = 0
        for i in range(len(ret)):
            ret[i] = ret[i] + acc
            acc = ret[i]
        for i in range(1, len(matrix)):
            for j in range(len(ret)):
                if j == 0:
                    ret[j] = ret[j] + matrix[i][j]
                else:
                    ret[j] = matrix[i][j] + min(ret[j-1], ret[j])
        return ret[-1]

class Solution:
    def minPathSum(self , matrix ):
        # write code here
        dp = [200005]*len(matrix[0])
        dp[0] = 0
        for i in range(len(matrix)):
            dp[0] = dp[0] + matrix[i][0]
            for j in range(1, len(matrix[0])):
                dp[j] = min(dp[j-1]+matrix[i][j], dp[j]+matrix[i][j])
        return dp[-1]

#
# 
# @param matrix int整型二维数组 the matrix
# @return int整型
#
class Solution:
    def minPathSum(self , matrix ):
        # write code here
        '''
        确实是很基础的二维动态规划。
        思路与递归正好相反：自顶向下的生成路径和，自底向上的查找最小路径和。
        dp[i][j]:从左上点(0,0)到点(i,j)的最小路径和。
        初始化：dp数组维度为m*n，初始化每个元素为0。第0行和第0列的最小路径和就是其行列和。先行加和初始化第0行和第0列。
        当然也可以不做此操作，初始化dp数组维度为m+1，n+1，且第0行第0列的第二个元素初始化为0（保证dp[1][1]=mat[0][0]），其他初始化为正无穷即可。
        递推公式：dp[i][j] = min(dp[i-1][j],dp[i][j-1])+matrix[i][j]
        时间复杂度：O(mn),空间复杂度：O(mn)/O(n)。
        可以进行空间压缩，由于我们的计算只涉及左边元素和上面元素，所以只需要一个2*n的空间即可（滚动数组）
        '''
        m , n = len(matrix),len(matrix[0])
        dp = [[100000000]*(n+1) for _ in range(2)]
        dp[0][1],dp[1][1] = 0,0
        for i in range(1,m+1):
            
            for j in range(1,n+1):
                dp[i%2][j] = min(dp[(i-1)%2][j],dp[i%2][j-1])+matrix[i-1][j-1]
        return dp[i%2][n]
        
#         m , n = len(matrix),len(matrix[0])
#         dp = [[100000000]*n for _ in range(m)]
#         dp[0][0] = matrix[0][0]
#         for i in range(1,m):
#             dp[i][0] = dp[i-1][0]+matrix[i][0]
#         for i in range(1,n):
#             dp[0][i] = dp[0][i-1]+matrix[0][i]
#         for i in range(1,m):
#             for j in range(1,n):
#                 dp[i][j] = min(dp[i-1][j],dp[i][j-1])+matrix[i][j]
#         #print(dp)
#         return dp[m-1][n-1]
        
#         '''
#         递归思路：每次选择向右或向下的最短路径。
#         时间复杂度：我没算错的话是O(2^mn)，空间复杂度由于调用系统栈其实也是这么多，铁定超时。
#         （因为递归是遍历所有的路径，自顶向下的查询。）
#         '''
#         self.m,self.n = len(matrix)-1,len(matrix[0])-1
#         def minpsum(i,j):
#             if i == self.m and j == self.n:
#                 return matrix[i][j]
#             if i == self.m:
#                 return matrix[i][j]+minpsum(i, j+1)
#             if j == self.n:
#                 return matrix[i][j]+minpsum(i+1, j)
#             right = minpsum(i, j+1)
#             down = minpsum(i+1, j)
#             return matrix[i][j]+min(right,down)
#         return minpsum(0, 0)