DP 2D

Table of Contents

• 118. Pascal's Triangle (Easy)
• 119. Pascal's Triangle II (Easy)
• 62. Unique Paths (Medium)
• 63. Unique Paths II (Medium)

118. Pascal's Triangle

• LeetCode | LeetCode CH (Easy)

• Tags: array, dynamic programming

• Generate the first numRows of Pascal's triangle.

                 numRows    index
     1              1         0
    1 1             2         1
   1 2 1            3         2
  1 3 3 1           4         3
 1 4 6 4 1          5         4

118. Pascal's Triangle - Python Solution

from typing import List


def generate(numRows: int) -> List[List[int]]:
    dp = [[1] * i for i in range(1, numRows + 1)]

    if numRows <= 2:
        return dp

    for i in range(2, numRows):
        for j in range(1, i):
            dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]

    return dp


print(generate(numRows=5))
#     [[1],
#    [1, 1],
#   [1, 2, 1],
#  [1, 3, 3, 1],
# [1, 4, 6, 4, 1]]

119. Pascal's Triangle II

• LeetCode | LeetCode CH (Easy)

• Tags: array, dynamic programming

• Return the rowIndexth row of Pascal's triangle.

119. Pascal's Triangle II - Python Solution

from typing import List


def getRow(rowIndex: int) -> List[int]:
    dp = [[1] * (i + 1) for i in range(rowIndex + 1)]

    if rowIndex <= 1:
        return dp[rowIndex]

    for i in range(2, rowIndex + 1):
        for j in range(1, i):
            dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]

    return dp[-1]


print(getRow(rowIndex=3))  # [1, 3, 3, 1]

62. Unique Paths

• LeetCode | LeetCode CH (Medium)

• Tags: math, dynamic programming, combinatorics

• Count the number of unique paths to reach the bottom-right corner of a m x n grid.

62. Unique Paths - Python Solution

# DP - 2D
def uniquePaths(m: int, n: int) -> int:
    if m == 1 or n == 1:
        return 1

    dp = [[1] * n for _ in range(m)]

    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]


print(uniquePaths(m=3, n=7))  # 28
# [[1, 1, 1,  1,  1,  1,  1],
#  [1, 2, 3,  4,  5,  6,  7],
#  [1, 3, 6, 10, 15, 21, 28]]

62. Unique Paths - C++ Solution

#include <iostream>
#include <vector>
using namespace std;

int uniquePaths(int m, int n) {
    vector dp(m, vector<int>(n, 1));

    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }

    return dp[m - 1][n - 1];
}

int main() {
    int m = 3, n = 7;
    cout << uniquePaths(m, n) << endl;  // 28
    return 0;
}

63. Unique Paths II

• LeetCode | LeetCode CH (Medium)

• Tags: array, dynamic programming, matrix

• Count the number of unique paths to reach the bottom-right corner of a m x n grid with obstacles.

63. Unique Paths II - Python Solution

from typing import List


# DP - 2D
def uniquePathsWithObstacles(obstacleGrid: List[List[int]]) -> int:
    if obstacleGrid[0][0] == 1 or obstacleGrid[-1][-1] == 1:
        return 0

    m, n = len(obstacleGrid), len(obstacleGrid[0])
    dp = [[0] * n for _ in range(m)]

    for i in range(m):
        if obstacleGrid[i][0] == 0:
            dp[i][0] = 1
        else:
            break

    for j in range(n):
        if obstacleGrid[0][j] == 0:
            dp[0][j] = 1
        else:
            break

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

    return dp[-1][-1]


obstacleGrid = [[0, 0, 0], [0, 1, 0], [0, 0, 0]]
print(uniquePathsWithObstacles(obstacleGrid))  # 2
# [[1, 1, 1],
#  [1, 0, 1],
#  [1, 1, 2]]

Comments