DP - Matrix

Algorithms
dp
Catalogue
  1. 1. Count
    1. 1.1. 62. Unique Paths
      1. 1.1.1. Follow Up
    2. 1.2. 63. Unique Paths II
    3. 1.3. 118. Pascal’s Triangle
    4. 1.4. 119. Pascal’s Triangle II
  2. 2. Minimum
    1. 2.1. 64. Minimum Path Sum

Count

62. Unique Paths

1
2
3
4
5
6
7
8
9
10
11
12
13
# Time : O(mn), Space : O(mn)
class Solution:
    def uniquePaths(self, m, n):
        dp = [[0] * n for _ in range(m)]
        for i in range(m):
            dp[i][0] = 1
        for j in range(n):
            dp[0][j] = 1

        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
        return dp[-1][-1]
1
2
3
4
5
6
7
8
9
# Time : O(mn), Space : O(n)
class Solution:
    def uniquePaths(self, m, n):
        dp = [1] * n

        for i in range(1, m):
            for j in range(1, n):
                dp[j] += dp[j-1]
        return dp[-1]

Follow Up

  1. Given three points in the matrix, find the path number that traverse these 3 points
  • do it seperated three matrix, then add together
  1. How to validate the three points?
  2. If give you a “H”, ask your path have to cross “H”

63. Unique Paths II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid):
        if not obstacleGrid:
            return 0
        m, n = len(obstacleGrid), len(obstacleGrid[0])
        dp = [0] * (n + 1)
        dp[0] = 1
        for i in range(n):
            dp[i+1] = 0 if obstacleGrid[0][i] else dp[i]

        for i in range(1, m):
            if obstacleGrid[i][0] == 1:
                dp[1] = 0  
            for j in range(1, n):
                if obstacleGrid[i][j] == 1:
                    dp[j+1] = 0
                else:
                    dp[j+1] += dp[j]
        return dp[-1]

118. Pascal’s Triangle

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
    def generate(self, numRows):
        if numRows == 0:
            return []

        res = [[1]]
        for i in range(1, numRows):
            cur = [1]
            for j in range(1, i):
                cur.append(res[-1][j-1] + res[-1][j])
            cur.append(1)
            res.append(cur)
        return res

119. Pascal’s Triangle II

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
    def getRow(self, rowIndex):
        if rowIndex == 0:
            return [1]

        prev = [1]
        for i in range(1, rowIndex+1):
            cur = [1]
            for j in range(1, i):
                cur.append(prev[j-1]+prev[j])
            cur += [1]
            prev = cur
        return cur

Minimum

64. Minimum Path Sum

  • Time : O(mn), Space : O(min(m, n))
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    class Solution(object):
        def minPathSum(self, grid):
            if not grid:
                return 0

            m, n = len(grid), len(grid[0])

            dp = [0] * n
            for i in range(n):
                dp[i] = grid[0][i] + (dp[i-1] if i >0 else 0)

            for i in range(1, m):
                for j in range(n):
                    if j == 0:
                        dp[j] += grid[i][j]
                        continue
                    dp[j] = min(dp[j], dp[j-1]) + grid[i][j]
            return dp[-1]
Share