动态规划算法练习（4）--medium

生信编程日常

修改于 2023-09-23 15:02:54

3960

文章被收录于专栏：生物信息学、python、R、linux生物信息学、python、R、linux

1. Minimum Path Sum

求从m x n的matrix中的左上角到右下角的最小和，只能向右或下移动。

个人感觉这个题其实与全局比对算法很像，只是这个不用考虑左上角这个方向（不考虑斜着的情况）。以下是实现方法（未经优化）：

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])
        path = [[0 for x in range(n)]  for y in range(m)]
        
        path[0][0] = grid[0][0]
        for x in range(1,m):
            path[x][0] = path[x-1][0] + grid[x][0]
        for y in range(1, n):
            path[0][y] = path[0][y-1] + grid[0][y]
            
        for i in range(1, m):
            for j in range(1, n):
                path[i][j] = min(path[i-1][j], path[i][j-1]) + grid[i][j]
                
        return path[-1][-1]

2. Minimum Falling Path Sum

与上题相似，不过这是一个方阵，并且下一行的所在的列必须与上一行的列不能超过一列。比如第一行第一列不能到第二行第三列（见例子）。

这个解题时需要考虑边界：

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])
        path = [[0 for x in range(n)]  for y in range(m)]
        
        path[0][0] = grid[0][0]
        for x in range(1,m):
            path[x][0] = path[x-1][0] + grid[x][0]
        for y in range(1, n):
            path[0][y] = path[0][y-1] + grid[0][y]
            
        for i in range(1, m):
            for j in range(1, n):
                path[i][j] = min(path[i-1][j], path[i][j-1]) + grid[i][j]
                
        return path[-1][-1]

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

如有侵权请联系 cloudcommunity@tencent.com 删除

matrix