有一个序列{a1，a2，a3，a4，...... aN}。运行是序列的最大严格递增或严格递减的连续部分。例如。如果我们有一个序列 {1,2,3,4,7,6,5,2,3,4,1,2} 我们有 5 次可能的运行 {1,2,3,4,7}, {7, 6,5,2}、{2,3,4}、{4,1} 和 {1,2}。
给定四个数字 N、M、K、L。计算 N 个数字的可能序列的数量，其中恰好有 M 次运行，序列中的每个数字小于或等于 K，并且相邻数字之间的差小于等于到 L
这个问题是在一次采访中被问到的。
我只能想到一个蛮力解决方案。这个问题的有效解决方案是什么？
这可以改写为重复问题。将您的问题视为找到 #(N, M) （假设 K 和 L 是固定的，它们用于重复条件，因此相应地传播）。现在从更受限制的计数函数 A(N, M; a) 和 D(N, M, a) 开始，其中 A 对最后一次运行升序的集合进行计数，D 对最后一次运行降序的集合进行计数，a 是集合中的最后一个元素。
用 A(N, M; a) 和 D(N, M; a) 表示 #(N, M) （它是所有允许的 a 的总和）。您可能会注意到两者之间存在关系（例如反射 A(N, M; a) = D(N, M; Ka)），但这对于计算来说并不重要，除了加快表格填充速度。
现在 A(N, M; a) 可以表示为 A(N-1, M; w), A(N-1, M-1; x), D(N-1, M; y) 和D（N-1，M-1；z）。这个想法是，如果你从一组大小 N-1 开始，并且知道最后一次运行的方向和最后一个元素的值，你就知道添加元素 a 是添加到现有运行还是添加运行。因此，您可以计算从前一个案例的可能性中获得您想要的东西的可能方法的数量。
我会让你把这个递归写下来。请注意，这是您考虑 L（仅将遵守 L 距离限制的那些）和 K（寻找最终情况）的地方。
使用 A(1, 1; a) = 1, A(1, x>1; a) = 0 的事实终止递归（对于 D 也是如此）。
现在，由于这是一个多重递归，请确保您的实现将结果存储在一个表中，并从尝试查找开始（通常称为动态编程）。
使用动态规划。对于子字符串中的每个数字，维护最大增加和最大减少子序列的单独计数。当您将新数字增量添加到末尾时，您可以使用这些计数来更新新数字的计数。复杂度：O(n^2)
我想您所说的“蛮力解决方案”是指“涉及 N、M、K、L 上的嵌套循环的直接解决方案”？有时，简单的解决方案就足够了。直接解决方案足够好的情况之一是您没有更好的解决方案。另一个时候是数字不是很大的时候。
有了这个，我会以相反的方向写循环，或者类似的东西。我是说：
除非有人证明，否则这是最有效的解决方案。