파이썬에서 k개의 가방에 n개의 사탕을 분배하는 방법의 수를 세는 프로그램

<시간/>

n개의 캔디와 캔디를 넣어야 하는 k개의 가방이 있다고 가정합니다. 우리는 각 가방에 적어도 하나의 사탕이 들어 있도록 사탕을 분배할 수 있는 가능한 방법의 수를 찾아야 합니다. 이 시나리오의 모든 사탕은 고유하므로 사탕을 가방에 넣을 수 있는 모든 가능한 방법을 계산해야 합니다.

따라서 입력이 n =3, k =2인 경우 출력은 3이 됩니다.

사탕은 이런 식으로 넣을 수 있습니다 -

(1, 2), (3)
(1) , (2, 3)
(2), (1, 3)

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

dp :=값 1로 초기화된 크기 n x n의 행렬
범위 2에서 n까지의 c에 대해 수행
- 범위 1에서 (c, k)의 최소값까지 b에 대해 수행
  - dp[c, b] :=dp[c-1, b-1] + dp[c-1, b] * (b+1)
반환 dp[n-1, k-1]

예

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

def solve(n, k):
   dp = [[1] * n for _ in range(n)]
   for c in range(2, n):
      for b in range(1,min(c,k)):
         dp[c][b] = dp[c-1][b-1] + dp[c-1][b] * (b+1)
   return dp[n-1][k-1]

print(solve(3, 2))

입력

3, 2