ABC271D - Flip and Adjust

考え方

dp[i][j] = iコ目まですべてを使ってjにできる方法（HとTの文字列）．

i + 1に遷移できるためには，dp[i][]が$i$コの文字列からなる必要がある．

回答例

初期化ではダミーの文字$X$を入れることで，遷移できるものを区別した．

N, S = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]

dp = [[] for _ in range(S + 1)]
dp[0].append('X')
for i in range(N):
    a, b = AB[i]
    for j in range(S, -1, -1):
        if 0 <= j - a and len(dp[j - a]) == i + 1:
            dp[j] = dp[j - a] + ['H']
        if 0 <= j - b and len(dp[j - b]) == i + 1:
            dp[j] = dp[j - b] + ['T']

if len(dp[S]) == N + 1:
    print('Yes')
    print(''.join(dp[S][1:]))
else:
    print('No')