algorithm - 找出 N 个不同高度的人的排列数量，使得他们中的 K 个从前面可见

Question

如何找到将 N 个不同高度的人(可能有些人高度相同)排列在队列中的方式的数量，使得从队列前面看时最多可见 K 个。如果一个人高度 H 并且从前面看不到，那么从前面看不到他身后任何较矮(或等高)的人。另外，如果从前面可以看到高度 H 的人。然后，从前面看不到任何在他身后且高度小于或等于 H 的人。或者简单地说，一个人从前面是可见的，当且仅当他面前的所有人都严格比他矮。

例子:
如果三个人的高度 = {1,2,3}然后在以下安排:
1->2->3(1在前)
1->3->2
2->1->3
2->3->1
3->1->2
3->2->1
我们可以看到以下人数:
3
2
2
2
1
1
分别。
注意:N 的值将是 (100) 的数量级。我想我们可以有一个动态规划解决方案，但我无法弄清楚。
非常感谢任何帮助。

Answer 1

编辑:这不适用于多人高度相同的情况。

我认为您可以通过考虑最高的人以及他是否排在队列的后面来重复出现。假设我们正在寻找 n 个人和可以看到的 k 人。

假设最高的人排在队列的末尾。他总是可以被看到所以k可以看到的配置数是剩余n-1人中的k-1可以看到的配置数被看见。

假设他不在队列的末尾。然后永远看不到队列末尾的那个人。因此，我们需要找到k 人可以从不在队列末尾的n-1 中看到的方式的数量。但是有 n-1 个人可以排在队列的末尾，因此配置的数量将是 n-1 倍，就好像我们真的在看一个较小的案例。

所以递归是

T(n,k) = T(n-1, k-1) + (n-1) * T(n-1, k)

我现在没有时间把它变成一个动态规划解决方案，但边界条件等应该很简单。