[已解决]Python：每日一题 391

def shortestWay(matrix):
    for i in range(len(matrix)):
        for j in range(len(matrix[0])):
            if i and j:
                matrix[i][j]+=min(matrix[i-1][j],matrix[i][j-1])
            elif i:
                matrix[i][j]+=matrix[i-1][j]
            elif j:
                matrix[i][j]+=matrix[i][j-1]

    return matrix[-1][-1]

class Solution:
    def minPathSum(self, grid):
        m,n=len(grid),len(grid[0])
        for _ in range(1,n):grid[0][_]+=grid[0][_-1]  #第一行的路径和
        for _ in range(1,m):grid[_][0]+=grid[_-1][0]  #第一列的路径和

        for i in range(1,n):
            for j in range(1,m):
                grid[j][i]+=min(grid[j-1][i],grid[j][i-1])   #然后分别一列一列的求出最短路径和


        return grid[m-1][n-1]     #最后一个就是求出的最小路径和

if __name__ == "__main__":
      obj = Solution()
        
      s=[
         [131,673,234,103,18],
         [201,96,342,965,150],
         [630,803,746,422,111],
         [537,699,497,121,956],
         [805,732,524,37,331]
         ]
      print(obj.minPathSum(s))

def daily391(grid: list) -> int:
    if not grid:
        return 0
    row, column = len(grid), len(grid[0])
    dp = [[0] * column for _ in range(row)]
    dp[0][0] = grid[0][0]
    for i in range(1, column):
        dp[0][i] = grid[0][i] + dp[0][i - 1]
    for i in range(1, row):
        dp[i][0] = grid[i][0] + dp[i - 1][0]
        for j in range(1, column):
            dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
    pprint(dp)
    return dp[-1][-1]

def shortest_path(matrix):
    dp = [];
    for i in range(0, len(matrix)):
        line = [];
        for j in range(0,len(matrix[i])):
            line.append(0);
        dp.append(line);
    dp[0][0] = matrix[0][0];
    for i in range(1, len(matrix[0])):
        dp[0][i] = dp[0][i-1] + matrix[0][i]
    for i in range(1,len(matrix)):
        dp[i][0] = dp[i-1][0] + matrix[i][0]
    for i in range(1, len(matrix)):
        for j in range(1, len(matrix[i])):
            if dp[i][j-1] < dp[i-1][j]:
                dp[i][j] = dp[i][j-1] + matrix[i][j];
            else:
                dp[i][j] = dp[i-1][j] + matrix[i][j];
    return dp[len(matrix)-1][len(matrix[0])-1];

def f391(List):
    if not List or not List[0]:
        return 0
    m, n = len(List), len(List[0])
    for i in range(m):
        for j in range(n):
            if i == 0 and j == 0:
                continue
            elif i == 0 and j > 0:
                List[i][j] += List[i][j-1]
            elif i > 0 and j == 0:
                List[i][j] += List[i-1][j]
            else:
                List[i][j] += min(List[i-1][j], List[i][j-1])                                         
    #print(List)
    return List[-1][-1]

def daily391_0(grid: list) -> int:
    if not grid:
        return 0
    row, column = len(grid), len(grid[0])
    steps = [sum(grid[0][:i]) for i in range(1, column + 1)]
    for i in range(1, row):
        steps[0] += grid[i][0]
        for j in range(1, column):
            steps[j] = min(steps[j - 1], steps[j]) + grid[i][j]
    return steps[-1]

def f391(M):
    for i in range(len(M)):
        for j in range(len(M[0])):
            if i and j:
                M[i][j]+=min(M[i-1][j],M[i][j-1])
            elif i:
                M[i][j]+=M[i-1][j]
            elif j:
                M[i][j]+=M[i][j-1]
    return M[-1][-1]

def f(list1):
    list2 = []
    for index in range(0,len(list1)):
        list2.append([0 for i in range(0,len(list1[0]))])
    list2[0][0] = list1[0][0]
    for n in range(1,len(list2[0])):
        list2[0][n] = list2[0][n-1] + list1[0][n]
    for n in range(1,len(list2)):
        list2[n][0] = list2[n-1][0] + list1[n][0]
    for m in range(1,len(list1)):
        for n in range(1,len(list1[0])):
            list2[m][n] = min(list2[m-1][n],list2[m][n-1]) + list1[m][n]
    return list2[-1][-1]

def f391(ls):
    for i in range(len(ls)):
        for j in range(len(ls[0])):
            if i!=0 and j==0:
                ls[i][j]+=ls[i-1][j]
            if j!=0 and i==0:
                ls[i][j]+=ls[i][j-1]
            if i!=0 and j!=0:
                ls[i][j]+=min(ls[i-1][j],ls[i][j-1])             
    return ls[-1][-1]