[알고리즘/백준] 2225: 합분해(python)

	n=1	n=2	n=3	n=4
k=1	1	1	1	1
k=2	2	3	4	5
k=3	3	6	10	15

이 테이블을 보면 dp[k][n] = dp[k-1][n] + dp[k][n-1] 의 규칙을 보이는걸 알 수 있다.

N, K = map(int, input().split())
dp = list([0] * (N+1) for _ in range(K+1))

for i in range(N + 1):
    dp[1][i] = 1
for i in range(2, K + 1):
    dp[i][1] = i
    for j in range(2, N + 1):
        dp[i][j] = (dp[i][j-1] + dp[i-1][j]) % 1000000000
print(dp[K][N])