动态规划找到所有可能的团队组合
Dynamic Programming Find All Possible Team Combinations
我一直在尝试解决一个问题，我必须计算一项随机运动的可能团队编队数量。
输入是这样的：
P → Number of Team Players
R → Roles
[Min, Max] → Role 0
[Min, Max] → Role 1
...
[Min, Max] → Role r-1
----------
Min= Minimum number of Players for the Role
Max= Maximum number of Players for the Role
以Sport1为例。假设 Sport1 是 3 种类型的角色（A、B、C），现在让我们假设每支球队有 8 名球员。
8 → Number of Team Players
3 → Roles
[3 , 7] → Role A
[1 , 5] → Role B
[0 , 2] → Role C
Valid team formations:
[3-5-0 , 3-4-1, 3-3-2, 4-4-0, 4-3-1, 4-2-2, 5-3-0, 5-2-1, 5-1-2, 6-2-0, 6-1-1, 7-1-0]
Number of valid Team Formations: 12
我已经通过遍历所有可能的阵型解决了这个问题，如果每个角色中的球员总和等于团队球员的数量，那么最终结果加一。否则加零 a.k.a。对下一个组合做同样的事情，直到没有结束。
3+5+0 = 8 → 有效组队。
3+5+1 > 8 → 组队无效
3+4+0 < 8 → 组队无效
这一切都是有趣的游戏，直到玩家数量达到 40 左右，角色数量达到 20 左右，每个角色的最小值 = 0 和最大值 = 40。
示例：
40
20
[0; 40] → Role A
[0; 40] → Role B
...
[0; 40] → Role T
在这种情况下，我需要检查 40^20 个可能的编队，因为我已经通过仅对角色 A 0 进行了一些削减，然后乘以 20，但仍然需要检查 40^19 个不同的组合.
这个问题必须用动态规划来解决。我已经使用 DP 解决了一些问题（序列问题、最大利润草莓箱），但似乎找不到解决这个问题的方法。
有人可以给出一些关于如何解决这个问题的提示 and/or 我可以在网上或书中找到类似的问题，这些问题可以引导我找到 DP 解决方案吗？
动态规划问题通常以您按顺序排列问题的各个部分而告终，这样您就可以从左到右解决它们，在第 n 阶段做足够的工作，以便您可以参考它以获取所有信息在阶段 n+1.
在这里您可以将前 n 个角色视为前 n 个阶段，因此您的示例中的前 n 行如“[Min, Max] → Role 0”。在第 n 阶段，对于最大 P 的所有可用玩家数量，我将计算仅使用前 n 个角色和最多该数量的玩家可以组成的不同阵型的数量。
在第 n+1 阶段，对于每个可用的玩家数量，我会考虑角色 n+1 中的所有合法玩家数量。从我目前正在考虑的球员数量中减去它，我得到前 n 个角色剩下的球员数量，我查找存储在那里的答案以获得前 n 个角色的不同阵型的数量。将这些可能性相加，我得到了我可以使用该数量的球员来弥补前 n+1 个角色的阵型数量。显然，我对直到 P 的所有数字重复此操作以获得我需要为阶段 n+1 存储的答案——除非这是最后阶段，在这种情况下只需要 P 个玩家的答案。
如果你做的决定可以从左到右分阶段排列，每个阶段的答案不依赖于太多信息，可以从前面阶段的答案计算出来，那么动态规划通常是一个实用的解决问题的方法。如果你准备在每个阶段存储和计算大量的可能性，你几乎可以将任何问题转化为动态规划问题，但最终这个数字变得如此之大以至于所谓的解决方案变得非常不切实际。
举个例子，在上面的问题中，第二阶段是以下只有两个角色 A 和 B 的问题。
[3 , 7] → 角色 A
[1 , 5] → 角色 B
原题中，如果P=8，即你的队伍有8人，你需要求出不同阵型的总数。第二阶段的问题是，如果只有两个角色，计算阵数，但是你需要计算0人、1人、2人……最多8人的阵数。然后当你计算出第三阶段的答案时，你可以说 "If I put 3 players in role C I have 5 players left and two roles left and I can look at the answer I have already calculated for the two-role problem with 5 players to see how many formations there are with 3 players in role C."
我一直在尝试解决一个问题，我必须计算一项随机运动的可能团队编队数量。
输入是这样的：
P → Number of Team Players
R → Roles
[Min, Max] → Role 0
[Min, Max] → Role 1
...
[Min, Max] → Role r-1
----------
Min= Minimum number of Players for the Role
Max= Maximum number of Players for the Role
以Sport1为例。假设 Sport1 是 3 种类型的角色（A、B、C），现在让我们假设每支球队有 8 名球员。
8 → Number of Team Players
3 → Roles
[3 , 7] → Role A
[1 , 5] → Role B
[0 , 2] → Role C
Valid team formations: [
3-5-0,3-4-1,3-3-2,4-4-0,4-3-1,4-2-2,5-3-0,5-2-1,5-1-2,6-2-0,6-1-1,7-1-0]Number of valid Team Formations: 12
我已经通过遍历所有可能的阵型解决了这个问题，如果每个角色中的球员总和等于团队球员的数量，那么最终结果加一。否则加零 a.k.a。对下一个组合做同样的事情，直到没有结束。
3+5+0 = 8 → 有效组队。
3+5+1 > 8 → 组队无效
3+4+0 < 8 → 组队无效
这一切都是有趣的游戏，直到玩家数量达到 40 左右，角色数量达到 20 左右，每个角色的最小值 = 0 和最大值 = 40。
示例：
40
20
[0; 40] → Role A
[0; 40] → Role B
...
[0; 40] → Role T
在这种情况下，我需要检查 40^20 个可能的编队，因为我已经通过仅对角色 A 0 进行了一些削减，然后乘以 20，但仍然需要检查 40^19 个不同的组合.
这个问题必须用动态规划来解决。我已经使用 DP 解决了一些问题（序列问题、最大利润草莓箱），但似乎找不到解决这个问题的方法。
有人可以给出一些关于如何解决这个问题的提示 and/or 我可以在网上或书中找到类似的问题，这些问题可以引导我找到 DP 解决方案吗？
动态规划问题通常以您按顺序排列问题的各个部分而告终，这样您就可以从左到右解决它们，在第 n 阶段做足够的工作，以便您可以参考它以获取所有信息在阶段 n+1.
在这里您可以将前 n 个角色视为前 n 个阶段，因此您的示例中的前 n 行如“[Min, Max] → Role 0”。在第 n 阶段，对于最大 P 的所有可用玩家数量，我将计算仅使用前 n 个角色和最多该数量的玩家可以组成的不同阵型的数量。
在第 n+1 阶段，对于每个可用的玩家数量，我会考虑角色 n+1 中的所有合法玩家数量。从我目前正在考虑的球员数量中减去它，我得到前 n 个角色剩下的球员数量，我查找存储在那里的答案以获得前 n 个角色的不同阵型的数量。将这些可能性相加，我得到了我可以使用该数量的球员来弥补前 n+1 个角色的阵型数量。显然，我对直到 P 的所有数字重复此操作以获得我需要为阶段 n+1 存储的答案——除非这是最后阶段，在这种情况下只需要 P 个玩家的答案。
如果你做的决定可以从左到右分阶段排列，每个阶段的答案不依赖于太多信息，可以从前面阶段的答案计算出来，那么动态规划通常是一个实用的解决问题的方法。如果你准备在每个阶段存储和计算大量的可能性，你几乎可以将任何问题转化为动态规划问题，但最终这个数字变得如此之大以至于所谓的解决方案变得非常不切实际。
举个例子，在上面的问题中，第二阶段是以下只有两个角色 A 和 B 的问题。
[3 , 7] → 角色 A
[1 , 5] → 角色 B
原题中，如果P=8，即你的队伍有8人，你需要求出不同阵型的总数。第二阶段的问题是，如果只有两个角色，计算阵数，但是你需要计算0人、1人、2人……最多8人的阵数。然后当你计算出第三阶段的答案时，你可以说 "If I put 3 players in role C I have 5 players left and two roles left and I can look at the answer I have already calculated for the two-role problem with 5 players to see how many formations there are with 3 players in role C."