다이나믹프로그래밍 DP 2D

m x n 의 2D 행렬(matrix) 문제에서 

 

- Brute Force 알고리즘 (DFS 사용) => Time: O(2^(n+m)), Space: O(n+m) <---- dfs, 재귀 사용

# Brute Force - Time: O(2 ^ (n + m)), Space: O(n + m)
def bruteForce(r, c, rows, cols):
    if r == rows or c == cols:
        return 0
    if r == rows - 1 and c == cols - 1:
        return 1
    
    return (bruteForce(r + 1, c, rows, cols) +  
            bruteForce(r, c + 1, rows, cols))

print(bruteForce(0, 0, 4, 4))

 

https://youtu.be/nKtKofRLX9M

 

- 메모이제이션(memoization, cache) => Time: O(n x m), Space: O(n x m) <---- hashmap 사용, Top-Down 방식으로..으로..

# Memoization - Time and Space: O(n * m)
def memoization(r, c, rows, cols, cache):
    if r == rows or c == cols:
        return 0
    if cache[r][c] > 0:
        return cache[r][c]
    if r == rows - 1 and c == cols - 1:
        return 1
    
    cache[r][c] = (memoization(r + 1, c, rows, cols, cache) +  
        memoization(r, c + 1, rows, cols, cache))
    return cache[r][c]

print(memoization(0, 0, 4, 4, [[0] * 4 for i in range(4)]))

 

https://youtu.be/n4N0fY1fsa8

 

- DP => Time: O(n x m), Space: O(m), m 은 열 개수 (# of cols) <---- Bottom-Up 방식으로..

# Dynamic Programming - Time: O(n * m), Space: O(m), where m is num of cols
def dp(rows, cols):
    prevRow = [0] * cols

    for r in range(rows - 1, -1, -1):
        curRow = [0] * cols
        curRow[cols - 1] = 1
        for c in range(cols - 2, -1, -1):
            curRow[c] = curRow[c + 1] + prevRow[c]
        prevRow = curRow
    return prevRow[0]

 

https://youtu.be/P1f2cfKPGrM