算可能的序列数 [英] Count Number of Possible Sequences

问题描述

我最近遇到下列问题接受记者采访时就来了。

I recently came across the following question during an interview.

有一个序列 {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} 。

There is a sequence {a1, a2, a3, a4, ..... aN}. A run is the maximal strictly increasing or strictly decreasing continuous part of the sequence. Eg. If we have a sequence {1,2,3,4,7,6,5,2,3,4,1,2} We have 5 possible runs {1,2,3,4,7}, {7,6,5,2}, {2,3,4}, {4,1} and {1,2}.

由于四个数字 N ， M ， K ，→。数一数 N 已完全 M 运行的数字，可能的序列的数量每个序列中的数量少小于或等于 K 和相邻数之差小于等于→。

Given four numbers N, M, K, L. Count the number of possible sequences of N numbers that has exactly M runs, each of the number in the sequence is less than or equal to K and difference between the adjacent numbers is less than equal to L.

推荐答案

有可能是一个方法来解析分析，并提出了一个O（1）解决方案。然而，这将需要很多人比我聪明弄清楚:)这里是一个动态编程解决方案。

There's probably a way to analyze it analytically and come up with an O(1) solution. However, that will take someone much smarter than me to figure out :) Here is a dynamic-programming solution.

我假设这个解决方案，所有的值必须为正数。此外，我假定序列中的所有值必须不等于前一个值。这两个条件似乎暗示，但从来没有明确规定，在问题。的

首先，让我们稍微改变问题，因此，除了以 N ， M ，<$ C $ ç> K 和→，我们也给出了序列中的最后一项的值，<子> N 。我们还可以添加的另一个的变量我，从而重新presents的最后一项是否是一个增加或减少序列的一部分。然后，我们将定义一个函数 F 返回给定的所有的这些值。可能的序列数

First, let's alter the problem slightly so that, in addition to N, M, K, and L, we are also given the value of the last term in the sequence, a_n. Let's also add yet another variable I, which represents whether that last term was part of an increasing or decreasing sequence. Then we'll define a function F to return the number of possible sequences given all of those values.

N = number of values in sequence
M = number of "runs" in the sequence
K = max value allowed
L = max difference between adjacent sequence terms
I = whether the last term is increasing or decreasing
an = last term in the sequence
FK,L(N,M,I,an) = number of possible sequences, given all these values

现在，如果我们有一个方法来计算 F ，我们可能只是总结的<子>在所有可能的n值的（从1到K）和我得到回答你的问题。

Now if we had a way to calculate F, we could just sum over all possible values of a_n (from 1 to K) and I to get the answer to your problem.

让我们假设我=越来越多。我们希望前preSS的 F <子> K，L （N，M，增加，一个<子> N ）中的术语对 F 小的价值，因此，我们可以递归地计算出 F 值，以获得最终值。我们将做到这一点，总结了 F 的价值超过了 <子>所有可能的值N-1 ;也就是说，我们基本上是说， F 等于长度数量的有效序列 N-1 的的可以的结束 <子> N ，然后我们想象追加 <子> N 以他们每个人。

Let's assume I = "increasing." We want to express F_K,L(N,M,"increasing",a_n) in terms of a "smaller" value of F, so we can recursively calculate values of F to obtain the final value. We'll do this by summing the value of F over all possible values of a_n-1; that is, we essentially say that F is equal to the number valid sequences of length N-1 that could end in a_n, then we imagine appending a_n to each of them.

由于我们知道 <子> N 是一个递增序列的一部分的（I =增加）的，我们知道， <子> N-1 ＆LT;一个<子> N （我们会得到另一种情况很快）的。我们也知道， <子> N-1 必须升在 <子> N-1 ;因此， MAX（1，<子> N - L）和LT = A <子> N-1 ＆LT;一个<子> N

Because we know a_n is part of an increasing sequence (I = "increasing"), we know that a_n-1 < a_n (we'll get to the other case soon). We also know that a_n-1 must be within L of a_n-1; thus max(1, a_n - L) <= a_n-1 < a_n.

我们现在有两个情况需要考虑，这取决于是否previous期限 <子> N-1 正在增加或减少：

We now have two cases to consider, depending on whether the previous term a_n-1 was increasing or decreasing:

1. <子> N-1 是增加的。然后，我们仍在增加，所以 F 的价值，我们感兴趣的是
   F <子> K，L （N-1，M，增加，一个<子> N-1 ）
2. <子> N-1 是减少的。 <子> N 现在的增加的，所以现在将是值多了一个跑。因此， F 的价值，我们感兴趣的是
   F <子> K，L （N-1，M-1，减少，一个<子> N-1 ）

1. a_n-1 was increasing. Then we are still increasing, so the value of F we're interested in is
   F_K,L(N-1,M,"increasing",a_n-1).
2. a_n-1 was decreasing. a_n is now increasing, so there's now going to be one more "run" of values. Thus, the value of F we're interested in is
   F_K,L(N-1,M-1,"decreasing",a_n-1).

我们总结所有这些情况下对所有可能的值 <子> N-1 得到的值的 F <子> K，L （N，M，增加，一个<子> N ）。我们可以发现的 F <子> K，L （N，M，减少，一个<子> N ）以类似的方式，只是我们限制<强>一<子> N-1 到 <子> N ＆LT;一个<子> N-1 ＆LT; =分钟（K，A <子> N + L），然后我们减去1从 M 的情况下，＃1，而不是情况＃2。

We sum all these cases for all possible values of a_n-1 to get the value of F_K,L(N,M,"increasing",a_n). We can find F_K,L(N,M,"decreasing",a_n) in a similar manner, only we limit a_n-1 to a_n < a_n-1 <= min(K, a_n+L), and we subtract 1 from M in case #1 rather than case #2.

最后，我们国家的基础情况。 F <子> K，L （N，M，I，一个<子> N ）：0，如果M＆LT; 1或M> N; 1，如果N = 1

Finally, we state the base cases. F_K,L(N,M,I,a_n): 0 if M < 1 or M > N; 1 if N = 1.

然后，正如我上面提到的，只是总结了的所有值我和 <子> N 在<强> F <子> K，L （N，M，I，一个<子> N ）得到回答你原来的问题。运行时的复杂性是 O（KMN）

Then, as I mentioned above, just sum over all values of I and a_n in F_K,L(N,M,I,a_n) to get the answer to your original problem. The runtime complexity is O(KMN)

这篇关于算可能的序列数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！