[1、n]の範囲の数値を含み、少なくとも1つのサブシーケンス{1,2,3,4 .... n}が存在するようにm個の要素のユニークな配列がいくつ存在するか。 ？制約に基づく可能な配列の組み合わせ
制約条件：m> n
私は組み合わせアプローチを考えました。しかし繰り返しがあります。 私のアプローチでは、まず1からnまでのすべての数字をレイアウトします。 たとえば、m = n + 1の場合、答えはn^2です。 （n個の斑点があり、範囲[1、n]の各数字） 今、さらなる計算のためのDP関係があると思いますが、私はそれを理解することができません。
ここでは、n = 3、m = 5の例を示します。緑の四角はサブシーケンスです。サブシーケンスは、配列の最初の1、最初1後だ最初の2で構成さなどのサブシーケンスの一部ではない四角は、彼らがサブシーケンスの終了後であればn値を取る、またはn-1値そうしますか。
したがって、この例に対する答えは簡単に力ずくで検証され1*9 + 3*6 + 6*4 = 51、です。係数1,3,6はPascal's triangleに関連しているように見えます。残りは読者に残されています。
dp [1] [1] = 1; （int i = 1; i <= n; i ++）{ dp [i] [0] = pow（n-1、i）; dp [i] [j] =（dp [i-1] [j-1] + n * dp [i-1] [j]） else [回答はdp [m] [n] ここまで分かりました。しかしこれはO（mn）です。私は線形時間で何かが必要です。 –
@ J.Doeここであなたのコメントが優れた答えにどのように関係しているのか分かりません。あなたは動的プログラミングの考え方に固執しているようですが、この答えは列挙型ソリューションに基づいた比較的単純な計算を示唆しています。 –
申し訳ありませんが、それを考え出しました。ありがとう。 –
問題を解決するために行ったことを教えてください。あなたはあなたの課題の質問をコピーして回答を得ることができるサイトではありません。 –
[email protected]_ [tag：malbolge]言語の解決策を教えてもらえますか？ –
@πάνταῥεῖ言語は問題ありません。私は効率的なアルゴリズムが必要です。線形/準線形時間で動作することができます。 –