資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝設計
法學Python程式：計算將n個糖果分到k個袋子裡的方法數
假設有n個糖果和k個袋子，需要將糖果放入袋子中。我們需要找出所有可能的糖果分配方式，使得每個袋子至少包含一個糖果。此場景中的每個糖果都是唯一的，因此我們必須計算所有可能的糖果分配方式。
例如，如果輸入為n = 3，k = 2，則輸出為3。
糖果可以這樣放置：
(1, 2), (3) (1) , (2, 3) (2), (1, 3)
為了解決這個問題，我們將遵循以下步驟：
dp := 一個n x n大小的矩陣，初始值為1
對於c從2到n，執行：
對於b從1到min(c, k)，執行：
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
更新於：2021年10月8日
496 次瀏覽
廣告