백준 알고리즘 13699번 점화식(python)

기본적인 다이나믹 프로그래밍 문제이다.

n = int(input())
dp = [0]*(36)
dp[0] = 1
dp[1] = 1
dp[2] = 2
for i in range(3, n+1):
    t = 0
    if i%2:
        for j in range(i//2):
            t += 2*dp[j]*dp[i-j-1]
        dp[i] = t + dp[i//2]**2
    else:
        for j in range(i//2):
            t += 2*dp[j]*dp[i-j-1]
        dp[i] = t
print(dp[n])