algorithm - 用3个常数计算可能性的算法？

我想计算他们有多少可能把一些随机瓶子装进一个箱子里我得到三个常数。

N = Count of Bottles
k = Count of Crates
K[num] = How many Bottles fit inside ONE Crate

例子：

N = 7; // 7 Bottles
k = 2; // 2 Crates
K1 = 3; // Crate 1 -> max 3 Bottles
K2 = 5; // Crate 2 -> max 5 Bottles

Above equals to 2 Possibilities:
1: First Crate 1 -> 3 bottles, Second crate -> 4 Bottles
2: First Crate -> 2 bottles, Second crate -> 5 Bottles

我的问题是，在我的例子中，计算结果的正确公式是什么，2种可能性？我怎样才能形成一个正确的公式，让我得到正确的可能性？任何帮助都将不胜感激。：）

最佳答案

您可以使用动态编程来查找t（n，k），这意味着“我们可以用多少种方法将n个瓶子填满第k个板条箱”。

T(0, 0) = 1
T(n, 0) = 0
T(n, k) = sum{1<=i<=K[k], T(n-i, k-1)}

下面是python中的一个示例实现（使用递归，无记忆）：

def T(n, k, K):
    if k==0: return n==0
    return sum(T(n-i, k-1, K) for i in xrange(1, K[k-1]+1))

print T(7, 2, [3, 5])