“leetcodeDP”

class Solution:

    def minimumTotal(self, triangle: List[List[int]]) -> int:

        # [2],

        # [3,4],

        # [6,5,7],

        # [4,1,8,3]

        # dp[k][i] += min(dp[k-1][i-1], dp[k-1][i])

        n = len(triangle)

        for i in range(1, n):

            m = i + 1

            for j in range(m):

                if j == 0:

                    triangle[i][j] += triangle[i-1][j]

                elif j == m-1:

                    triangle[i][j] += triangle[i-1][j-1]

                else:

                    triangle[i][j] += min(triangle[i-1][j-1], triangle[i-1][j])

        return min(triangle[-1])

class Solution:

    def minPathSum(self, grid: List[List[int]]) -> int:

        n = len(grid)

        m = len(grid[0])

        # 每次只能向下或者向右移动一步

        # -> dp[next] = min(dp[left], dp[up]) + dp[i]

        # 第一行只能从左往右，第一列只能从上往下

        for i in range(1, n):

            grid[i][0] += grid[i-1][0]

        for i in range(1, m):

            grid[0][i] += grid[0][i-1]

        for i in range(1, n):

            for j in range(1, m):

                grid[i][j] += min(grid[i-1][j], grid[i][j-1])

        return grid[n-1][m-1]

class Solution:

    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:

        n = len(obstacleGrid)

        m = len(obstacleGrid[0])

        @cache

        def dfs(i: int, j: int) -> int:

            # 如果到达右下角且右下角不为 1，则当前路线有效

            if i == n-1 and j == m-1 and obstacleGrid[i][j] != 1:

                return 1

            # 如果越界或者碰到阻碍，则无效

            if i >= n or j >= m or obstacleGrid[i][j] == 1:

                return 0

            # 返回 向左走向下走

            return dfs(i+1, j) + dfs(i, j+1)

        return dfs(0, 0)