acmicpc.net 2193(DP), 2579(DP), 2169(DP), 1932(DP)

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

앞의 1904번 문제하고 비슷하다.

#1 = [1]

#2 = [10]

#3 = [100, 101]

#4 = [1000, 1001, 1010]

#5 = [10000, 10001, 10010, 10100, 10101]

아랫쪽 파란색은 위쪽 파란색에서 만들어지고 빨간색도 그렇다. 색 표시 안한것들은

-2칸전의 값+01한 값이다. 피보나치처럼 계산하면 될거라는걸 알수있다.

# -*- encoding: cp949 -*-
#1 = [1]
#2 = [10]
#3 = [100, 101]
#4 = [1000, 1001, 1010]
#5 = [10000, 10001, 10010, 10100, 10101]
n = int(raw_input())
dp = [0 for i in xrange(91)]
dp[1] = 1; dp[2] = 1
for i in xrange(3,n+1):
    dp[i] = dp[i-1] + dp[i-2]
print dp[n]

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

잘 생각해보면. n번째 계단은 

max((n-2번째까지의 최대값 + n번째계단) , (n-3번째까지의 최대값 + n-1번째의 계단 + n번째계단))

이 점화식이다. 그렇게 식을 세워서 풀면 된다.

# -*- encoding: cp949 -*-
n=input()
stair = [input() for i in xrange(n)]
dp = [0 for i in xrange(n+1)]
dp[1] = stair[0]
dp[2] = stair[0]+stair[1]
for i in xrange(3,n+1):
    dp[i] = max(dp[i-2], dp[i-3] + stair[i-2]) + stair[i-1]
print dp[n]

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

로봇이 왼쪽,오른쪽 아래로만 가능하다. 위로 올라오는것까지 가능했으면 bfs로 어떻게 해봐야되나? 했을텐데 아래로만 가고, 1,1에서 n,m으로 가면 된다. dp리스트의 각각 줄에는 최대값을 넣어준다.

각각의 모든 수에 대해서 왼쪽에서 오는경우, 오른쪽에서 오는경우, 그냥 위에서 오는경우 중 가장 큰 값을 dp테이블에 넣고 한줄 한줄씩 진행한다.

# -*- encoding: cp949 -*-
n,m = map(int,raw_input().split())
maps = [map(int,raw_input().split()) for i in xrange(n)]
dp = [[0 for j in xrange(m)] for i in xrange(n)] #dp
dp[0][0] = maps[0][0] #시작점.
for i in xrange(1,m): #dp리스트의 첫 줄을 초기화해준다. 왼쪽에서 시작이므로 첫번째부터 더해준다.
    dp[0][i] = dp[0][i-1] + maps[0][i]
for i in xrange(1,n): #2번째 줄부터의 연산.
    l_r = [[0 for k in xrange(m)] for l in xrange(2)] 
    for j in xrange(m): #그냥 바로 위에서 내려올 경우.
        l_r[0][j] = l_r[1][j] = dp[i-1][j] + maps[i][j]
    for j in xrange(1,m): #max(왼쪽에서오는경우, 원래있는경우)
        l_r[0][j] = max(l_r[0][j], l_r[0][j-1] + maps[i][j])
    for j in xrange(m-2,-1,-1): #max(오른쪽에서 오는경우, 원래있는경우)
        l_r[1][j] = max(l_r[1][j], l_r[1][j+1] + maps[i][j])
    for j in xrange(m): #위의 값들중에서 가장 큰 값만 고른다.
        dp[i][j] = max(l_r[0][j], l_r[1][j])

#print '\n'.join(map(str,dp))
print dp[n-1][m-1]

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

# -*- encoding: cp949 -*-
n = int(raw_input())
tri = [[0]]+[map(int,raw_input().split()) for i in xrange(n)]
dp = [[0 for j in xrange(i)] for i in xrange(n+1)]
dp[1][0] = tri[1][0]
for i in xrange(2,n+1):
    dp[i][0] = dp[i-1][0] + tri[i][0] 
    dp[i][-1] = dp[i-1][-1] + tri[i][-1] 
    for j in xrange(1,i-1):
        dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + tri[i][j]
 
print max(dp[n])