[Python] 백준 2688번: 줄어들지 않아

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

2688번: 줄어들지 않아

1. 처음시작이 0, 1, 2, 3, 4 ..., 9 이다. 2번째는 처음에 앞에 자릿수를 하나씩 늘려주면 0(0, 1, 2, 3, 4... 9), 1(1, 2, 3, 4... 9), 2(2, 3, 4... 9), ...., 9(9) 이다. 3번째는 마찬가지로 두번째 dp에 자릿수를 하나씩 늘려주면된다.

 

0	1	2	3	4	5	6	7	8	9
1	1	1	1	1	1	1	1	1	1

0	1	2	3	4	5	6	7	8	9
1	1	1	1	1	1	1	1	1	1
10	9	8	7	6	5	4	3	2	1

0	1	2	3	4	5	6	7	8	9
1	1	1	1	1	1	1	1	1	1
10	9	8	7	6	5	4	3	2	1
55	45	36	28	21	15	10	6	3	1

0	1	2	3	4	5	6	7	8	9
1	1	1	1	1	1	1	1	1	1
10	9	8	7	6	5	4	3	2	1
55	45	36	28	21	15	10	6	3	1
220	165	120	84	58	35	20	10	4	1

import sys
input = sys.stdin.readline

T = int(input())
while T:
    T -= 1
    n = int(input())
    dp = [[0 for _ in range(10)] for _ in range(n+1)]
    for i in range(1, n+1):
        dp[i][0] = max(1, sum(dp[i-1]))
        for j in range(1, 10):
            dp[i][j] = max(1, dp[i][j-1] - dp[i-1][j-1])
    print(sum(dp[n]))