基於約束條件的可能數組組合

-2

有多少個m元素的唯一數組存在，使得它們包含範圍[1，n]中的數字並且存在至少一個子序列{1,2,3,4 .... n} ？基於約束條件的可能數組組合

限制條件：M> N

我想的組合的方法。但會有重複。在我的方法中，我首先列出從1到n的所有數字。例如，如果m = n + 1，則答案是n^2。（n個可用的點，範圍[1，n]中的每個數字）現在，我認爲可能有一個DP關係進一步計算，但我無法弄清楚。

來源

2016-07-24 J.Doe

請告訴我們你已經做了什麼來解決問題。 SO不是您可以複製粘貼您的作業問題並獲得答案的網站。 –

[email protected]_我可以給你一個[tag：malbolge]語言的解決方案，那可以嗎？ –

@πάνταῥεῖ語言不成問題。我只需要一個高效的算法。它可以在線性/亞線性時間運行。 –

下面是n = 3和m = 5的示例。綠色方塊是子序列。該子序列由陣列中的第一個1，第一個2之後的第一個1等構成。不屬於該子序列的正方形可以採取n值，如果它們在子序列結束之後，或者其他值爲n-1值。

所以，這個問題的答案的例子是1*9 + 3*6 + 6*4 = 51，這是很容易被蠻力驗證。係數1,3,6似乎與Pascal's triangle有關。其餘的留給讀者。

來源

2016-07-24 11:06:39 user3386109

dp [1] [1] = 1;對於（int i = 1; i <= n; i ++）{ dp [i] [0] = pow（n-1，i） } if（j == n）dp [i] [j] =（dp [i-1] [j-1] + n * dp [i-1] [j]） else dp [i] [ j] =（dp [i-1] [j-1] +（n-1）* dp [i-1] [j]）答案是dp [m] [n] 我想通了。但這是O（mn）。我需要線性時間。 –

@ J.Doe我看不出你的評論如何與這裏的優秀答案相關。您似乎陷入了動態編程的想法，但是這個答案表明基於枚舉解決方案的計算相對簡單。 –

對不起，算出來了。謝謝。 –

基於約束條件的可能數組組合

回答

相關問題