Pythonでk個のバッグにn個のキャンディーを配布する方法の数を数えるプログラム

キャンディーを入れなければならないキャンディーとバッグがn個あるとします。各バッグに少なくとも1つのキャンディーが含まれるように、キャンディーを配布できる方法の数を見つける必要があります。このシナリオのすべてのキャンディーはユニークであるため、キャンディーをバッグに入れて配布する可能性のあるすべての方法を数える必要があります。

したがって、入力がn =3、k =2の場合、出力は3になります。

キャンディーはこのように置くことができます-

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

これを解決するには、次の手順に従います-

• dp：=値1で初期化されたサイズnxnの行列

• 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

出力

3