acmicpc.net 2011(DP), 2240(DP), 2666(DP), 2624(DP)

https://www.acmicpc.net/problem/2011

# -*- encoding: cp949 -*-
import sys
sys.setrecursionlimit(10000000)
def password(index):
    if index < 0:
        return 1
    if dp[index] != 0: 
        return dp[index]

    if 0 < int(n[index]) < 10:
        dp[index] = password(index-1)%mod
    if index-1>=0 and 10 <= int(n[index-1:index+1]) <= 26:
        dp[index] += password(index-2)%mod
    return dp[index]%mod

dp = [0 for i in xrange(5002)]
mod = 1000000
n=raw_input()
print password(len(n)-1)
#print dp[:10]

https://www.acmicpc.net/problem/2240

3차원 리스트(배열)를 써서 해결해야함을 감으로 알수있다.

# -*- encoding: utf-8 -*-
import sys
sys.setrecursionlimit(10000000)
def eat(p, w, ct):
    if ct==t:
        return 0

    ret = dp[p][w][ct]
    if ret!=0: return ret

    temp,a,b = 0,0,0
    #식 = 현재 위치 자두 + max(안움직이고 다음 시간 자두, max(움직이고 현재 시간 자두, 움직이고 다음 시간 자두))
    if p==1:
        if jadu[ct]==p:
            temp += 1
        a = eat(1,w,ct+1)
        if w>0:
            b = max(eat(2,w-1,ct), eat(2,w-1,ct+1))
        temp += max(a,b)
    else:
        if jadu[ct]==p:
            temp += 1
        a = eat(2,w,ct+1)
        if w>0:
            b = max(eat(1,w-1,ct), eat(1,w-1,ct+1))
        temp += max(a,b)

    dp[p][w][ct] = max(dp[p][w][ct], temp)
    return dp[p][w][ct]

t,w=map(int,raw_input().split())
jadu = [input() for i in xrange(t)]
dp = [[[0 for k in xrange(t+1)] for j in xrange(w+1)] for i in xrange(3)] #바깥쪽 인덱스부터 현재 내 위치, 움직일수 있는 정도, 시간
print eat(1,w,0)

https://www.acmicpc.net/problem/2666

# -*- encoding: utf-8 -*-
def move(index, a, b):
    if index==m:
        return 0
    ret = dp[a][index]
    if ret!=0: return ret

    dp[a][index] = min(abs(door[index] - a) + move(index+1, door[index],b),\
                       abs(door[index] - b) + move(index+1, a, door[index]))
    return dp[a][index]

n=input()
open = map(int,raw_input().split())
m=input()
door = [input() for i in xrange(m)]
dp = [[0 for i in xrange(n+1)] for j in xrange(n+1)]
print move(0,open[0],open[1])

https://www.acmicpc.net/problem/2624

앞에 쉬운 동전문제인 http://qkqhxla1.tistory.com/683 의 2298문제와 비교해보자. 갯수 연산만 추가됨.

# -*- encoding: utf-8 -*-
T = input()
K = input()
coin = sorted([map(int,raw_input().split()) for i in xrange(K)], key=lambda x:x[0])
dp = [[0 for i in xrange(T+1)] for j in xrange(K+1)]
dp[0][0] = 1
for i in xrange(1,K+1):
    for j in xrange(coin[i-1][1]+1):
        for k in xrange(T+1):
            if k >= coin[i-1][0]*j:
                dp[i][k] += dp[i-1][k-coin[i-1][0]*j]

print dp[K][T]