[Python] Intermediate Low - DP

 

 

#subproblem을 그대로 합치면 되는 DP

 

- 피보나치 수

https://www.codetree.ai/missions/2/concepts/6/problems/fibonacci-number/description

코드트리

n = int(input())

def fibonacci(n):
    if n <= 1:
        return n
    F = [0 for i in range(n+1)]
    F[0] = 0
    F[1] = 1
    for i in range(2, n+1):
        F[i] = F[i-1] + F[i-2]
    return F[n]
print(fibonacci(n))

 

 

 

 

#격자 안에서 한 칸씩 전진하는 DP

 

- 정수 사각형 최대 합

https://www.codetree.ai/missions/2/concepts/6/problems/maximum-sum-path-in-square/description

코드트리

import sys
input = sys.stdin.readline

def ans(arr):
    for i in range(n):
        for j in range(n):
            if i == 0 and j == 0:
                dp[i][j] = arr[i][j]
            elif i == 0 and j != 0:
                dp[i][j] = arr[i][j] + dp[i][j-1]
            elif i != 0 and j == 0:
                dp[i][j] = arr[i][j] + dp[i-1][j]
            else:
                dp[i][j] = arr[i][j] + max(dp[i][j-1], dp[i-1][j])

n = int(input())
arr = [[] for i in range(n)]
dp = [[0 for i in range(n)] for i in range(n)]
for i in range(n):
    arr[i] = list(map(int, input().split()))

ans(arr)
print(max(max(dp)))

 

 

 

 

#String Matching

 

- 최장 공통 부분 수열

https://www.codetree.ai/missions/2/concepts/6/problems/longest-common-sequence/description

코드트리

def lcs(a, b):
    for i in range(1, len(a)+1):
        for j in range(1, len(b)+1):
            if a[i-1] == b[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i][j-1], dp[i-1][j])

a = input()
b = input()
dp = [[0 for i in range(len(b)+1)] for i in range(len(a)+1)]

lcs(a, b)
print(dp[-1][-1])

 

 

 

 

#아이템을 적절히 고르는 문제

 

- 동전 거슬러주기

https://www.codetree.ai/missions/2/concepts/6/problems/coin-change/description

코드트리

n, m = map(int, input().split())
coin = list(map(int, input().split()))
dp = [float('inf') for i in range(m+1)]
dp[0] = 0
for i in range(1, m+1):
    for j in range(1, n+1):
        if i >= coin[j-1]:
            dp[i] = min(dp[i], dp[i - coin[j-1]] + 1)

if dp[m] == float('inf'):
    print(-1)
else:
    print(dp[m])

아 이 문제는 너무 어려웠다.. 해설 다시 보면서 공부 더 해야 할 것 같다...

DP 점화식 고안하는 거 너무 어렵다.. 전에는 그래프가 더 어렵다고 생각했는데 나도 이제 DP가 더 어려운 단계(?)에 도착했구나.. 좋아해야돼..?