DP 점화식 손으로 정리하기(파이썬)

매주 화요일 오프라인 알고리즘 스터디를 하면서 'dp'파트는 

서로 5문제를 정해서 각자 점화식 도출방법을 정리해 오기로 했다 

내가 담당하는 문제들의 점화식을 직접 적으면서 도출해보았다 

느낀 점: dp는 점화식을 도출하기 위해  n=1,2,3....을 대입해 보는 것도 필승 전략 중 하나이다

 

1. 타일 채우기

2133번: 타일 채우기

def main():
    n = int(input())

    dp = [0] * 31

    dp[0] = 1
    dp[2] = 3

    for i in range(4, n + 1):
        dp[i] = dp[i - 2] * 3
        for j in range(4, i + 1, 2):
            dp[i] += dp[i - j] * 2

    print(dp[n])

if __name__ == "__main__":
    main()

 

2. 파도반 수열 

9461번: 파도반 수열

T = int(input()) # 테스트 케이스 개수 입력

for _ in range(T):
    N = int(input()) # 자연수 N 입력
    dp = [0] * 101 # dp 리스트 초기화

    # 초기값 설정
    dp[1], dp[2], dp[3] = 1, 1, 1
    dp[4], dp[5] = 2, 2

    # DP 계산
    for i in range(6, N+1):
        dp[i] = dp[i-1] + dp[i-5]

    print(dp[N]) # P(N) 출력

 

3. 합분해

2225번: 합분해

n,k=map(int,input().split())

d=[[1]*(k+1) for _ in range(n+1)] # 행:n, 열:k
for i in range(2,k+1):
    d[1][i]=i
for i in range(1,n+1):
    for j in range(2,k+1):
        d[i][j]=d[i-1][j]+d[i][j-1]

print(d[n][k]%1000000000)

 

4. 암호코드

2011번: 암호코드

MOD = 1000000  # 모듈러 연산 상수
dp = [0] * 5001


def solution(code, n):
    if code[0] == '0':
        return 0
    dp[0] = dp[1] = 1

    for i in range(2, n + 1):
        if code[i - 1] != '0':
            dp[i] = dp[i - 1] % MOD

        tmp = int(code[i - 2]) * 10 + int(code[i - 1])
        if 10 <= tmp <= 26:
            dp[i] = (dp[i] + dp[i - 2]) % MOD

    return dp[n]


if __name__ == "__main__":
    str = input()
    answer = solution(str, len(str))
    print(answer)

 

5. 이동하기

11048번: 이동하기

import sys

input = sys.stdin.readline

N, M = map(int, input().split())

# 그래프 생성 및 초기화
graph = []
for i in range(N):
    row = list(map(int, input().split()))
    graph.append(row)

# dp 배열 생성 및 초기화
dp = [[0] * M for _ in range(N)]
dp[0][0] = graph[0][0] # 시작 위치 초기화

# 첫 행 초기화
for j in range(1, M):
    dp[0][j] = dp[0][j-1] + graph[0][j]

# 첫 열 초기화
for i in range(1, N):
    dp[i][0] = dp[i-1][0] + graph[i][0]

# dp 배열 채우기
for i in range(1, N):
    for j in range(1, M):
        dp[i][j] = max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + graph[i][j]

# 결과 출력
print(dp[N-1][M-1])