シーケンス {a1, a2, a3, a4, ..... aN} があります。実行は、シーケンスの最大の厳密に増加または厳密に減少する連続部分です。例えば。シーケンス {1,2,3,4,7,6,5,2,3,4,1,2} がある場合、{1,2,3,4,7}、{7、 6,5,2}、{2,3,4}、{4,1}、{1,2}。
4 つの数値 N、M、K、L が与えられた場合。正確に M ランを含む N 数値の可能なシーケンスの数を数えます。シーケンス内の各数値は K 以下であり、隣接する数値間の差は等しくありません。 Lへ
インタビュー中に質問されました。
力ずくで解決するしか思いつきませんでした。この問題の効率的な解決策は何ですか?
これは、再発の問題と言い換えることができます。＃（N、M）を見つけるときに問題を見てください（KとLが固定されていると仮定すると、これらは繰り返し条件で使用されるため、それに応じて伝播します）。ここで、より制限されたカウント関数A（N、M; a）およびD（N、M、a）から始めます。ここで、Aは最後の実行が昇順のセットをカウントし、Dは最後の実行が降順のセットをカウントします。aは次の値です。セットの最後の要素。
＃（N、M）をA（N、M; a）およびD（N、M; a）で表現します（許容されるすべてのaの合計です）。2つの間に関係があることに気付くかもしれませんが（反射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上のネストされたループを含む単純なソリューション」とはどういう意味だと思いますか？単純な解決策で十分な場合もあります。簡単な解決策で十分な場合の1つは、より良い解決策がない場合です。もう1つの時期は、数がそれほど多くない場合です。
それを胸から外して、ループを逆方向に書くか、そのようなものにします。つまり：
誰かが別の方法で実証するまで、これが最も効率的な解決策です。