[python/伯準/DP]225:合計分解

質問する

に答える

Case 1)k=1の数

n = 1 (1)                                                      => 1개 
n = 2 (2)                                                      => 1개 
n = 3 (3)                                                      => 1개 

case 2) k = 2

n = 1 (0,1) (1,0)                                              => 2개 
n = 2 (0,2) (2,0) (1,1)                                        => 3개  
n = 3 (0,3) (3,0) (1,2) (2,1)                                  => 4개

case 3) k = 3

n = 1   (0,0,1) (0,1,0) (1,0,0)                                 => 3개  

n = 2    (0,0,2) (0,2,0) (2,0,0), (1,1,0) (1,0,1), (0,1,1)      => 6개  

n = 3   (0,0,3) (0,3,0), (3,0,0), (1,1,1), (1,2,0),
        (1,0,2), (0,1,2), (2,1,0), (2,0,1), (0,2,1)             => 10개 

n = 4   (0,0,4), (0,4,0), (4,0,0), (1,1,2), (1,2,1), 
        (2,1,1), (0,1,3), (1,0,3), (1,3,0), (0,3,1), 
        (3,0,1), (3,1,0), (2,2,0), (0,2,2), (2,0,2)            => 15개 

case 4) k = 4

    n = 1 				                                       => 4개 

    n = 2 			                                           => 10개 
        (0,0,0,2) -> 4!/3! -> 4개 
        (0,0,1,1) -> 4!/2!2! -> 6개 

    n = 3                                                      => 20개 
        (0,0,0,3) -> 4!/3! -> 4개
        (0,1,1,1) -> 4!/3! -> 4개
        (0,0,1,2) -> 4!/2! -> 12개

以上の内容は表形式で以下のように表現されている.

n=1の場合、kとなることが多い.
k=1の場合、常に1である.
kおよびnが2より大きい場合、dp[k][n]=dp[k−1][n]+dp[k][n−1]を決定することができる.(表参照)
だから点火式.dp[k][n] = dp[k-1][n] + dp[k][n-1] (단, k와 n은 1보다 큰 자연수).

コード#コード#

n, k = map(int, input().split())

dp = [[0]*201 for i in range(201)]

# k = 1, n =1 초기화 
for i in range(201):
    dp[i][1] = i
    dp[1][i] = 1

for i in range(2,201):
    for j in range(2,201):
        dp[i][j] = dp[i-1][j]+dp[i][j-1]

print(dp[k][n]%1000000000)