[DP] BOJ 2240 자두나무

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

import sys
from itertools import combinations
input = sys.stdin.readline
 
T, W = map(int, input().split())
tree = [0] + [int(input())-1 for t in range(T)]
 
dp = [[0] * (W + 1) for _ in range(T + 1)]    # W * T의 배열
for i in range(1, T+1):
    # 전혀 움직이지 않았을 경우 초기화
    if tree[i] == 0:
        dp[i][0] = dp[i-1][0] + 1
    else:
        dp[i][0] = dp[i-1][0]
        
    for j in range(1, W+1):
        # w번 움직이므로 2로 남은 나머지는 위치와 동일함
        if tree[i] == j % 2: # 먹는 경우
            # 과거의 위치에서 움직여서 먹는 경우, 현재의 위치에서 움직이지 않고 먹는 경우
            dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + 1
        else: # 먹지 못하는 경우
            # 과거의 위치에서 움직여서 먹지 못한는 경우, 현재 위치에서 먹지 못하는 경우
            dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) 
print(max(dp[T]))