Dynamic Programming (DP)

Donburi·2023년 2월 11일

CS DP 알고리즘 전공

알고리즘

목록 보기

2/3

Dynamic Programming (DP, 동적계획법)

Used for optimization problems - can find optimal solutions when Greedy fails
Main Idea: recursively define the value of an optimal solution using smaller problem sizes (optimal substructure)
- Optimal Substructure (최적 부분 구조): 매 순간의 최적해가 문제에 대한 최적해인 경우
Two methods
- Top-Down (Recursive): memoization
- Bottom-Up (Iterative): tabulation
Here, "programming" means "planning", not coding
- Fun Fact: DP was coined by Richard Bellman (yes, the same guy from the Bellman-Ford algorithm)

Problems

How to approach DP problems

Derive the recurrence relation (점화식) / 90%
Code / 10%

Maximum Subarray (연속합) / 1D

Kadane's Algorithm
v[i] = the (local) maximum subarray that ends at a[i]
(that is, either v[i-1]+a[i] or just itself a[i])

import sys

n = int(sys.stdin.readline())
a = list(map(int, sys.stdin.readline().split()))
v = [0]*n
v[0] = a[0]
largest = v[0]
for i in range(1, n):
    v[i] = v[i-1]+a[i]
    if v[i]<a[i]:
        v[i] = a[i]
    if v[i]>largest:
        largest = v[i]
print(largest)

O(n)
can be further optimised (we don't actually need v as for every i, we only need to know v[i-1])

Longest Increasing Subsequence (LIS) / 1D

lis[i] = the length of the LIS that ends at xi

import sys

n = int(sys.stdin.readline())
a = list(map(int, sys.stdin.readline().split()))
lis = [1]*n
for i in range(1, n):
    longest = -1
    for j in range(i):
        if a[i]>a[j]:
            longest = max(longest, lis[j])
    if longest!=-1:
        lis[i] += longest
print(max(lis))

O(n2): for every i, it takes O(i) time to calculate lis[i]

Alternative Solution using LCS

Let X = a, Y = sorted(a)
LCS(X, Y) is exactly the LIS of X

Longest Common Substring (LCS) / 2D

lcs[i][j] = the length of the LCS of X[1..i] and Y[1..j]

import sys

x = sys.stdin.readline().strip()
y = sys.stdin.readline().strip()
m = len(x)
n = len(y)
lcs = [[None]*(n+1) for _ in range(m+1)]
for i in range(m+1):
    for j in range(n+1):
        if i==0 or j==0:
            lcs[i][j] = 0
        elif x[i-1]==y[j-1]:
            lcs[i][j] = lcs[i-1][j-1]+1
        else:
            lcs[i][j] = max(lcs[i-1][j], lcs[i][j-1])
print(lcs[m][n])

O(mn)

0-1 Knapsack (0-1 배낭 문제) / 2D

dp[i][j] = the largest value possible using the first i items with knapsack capacity j

import sys

n, w = map(int, sys.stdin.readline().split())
wt = [0]
v = [0]
for _ in range(n):
    a, b = map(int, sys.stdin.readline().split())
    wt.append(a)
    v.append(b)
dp = [[0]*(w+1) for _ in range(n+1)]
for i in range(1, n+1):
    for j in range(1, w+1):
        if wt[i]<=j:
            dp[i][j] = max(v[i]+dp[i-1][j-wt[i]], dp[i-1][j])
        else:
            dp[i][j] = dp[i-1][j]
print(dp[n][w])