問題タブ [lis]

配列 = {2,5,7,8,10} とします。要素がその前のすべての要素の合計よりも小さくならないように、最長増加サブシーケンスの長さを見つける必要があります。

この場合、答えは {2,5,7}、{2,5,8}、または {2,8,10} になります。長さ = 3
これは O(n^2) で簡単に解けます。LIS の長さは O(n log n) で確認できます。問題は長さだけなので、この問題も O(n log n) で解けると思います。しかし、どうすればそれを行うことができますか?

これは標準的な動的プログラミングの質問LIS PROBLEMです

2D 座標のポイントの最長増加サブシーケンスが必要です

つまり、配列 のインデックス i にある 2 つの点 A(x1,y1) 、配列のインデックス j にある B(x2,y2) は、(x1<=x2) && (y1 <=y2) && の場合、増加シーケンスの一部になることができます。 !(x1==x2 && y1==y2) && (j>i)

私のコードは以下のとおりです。これは、標準の DP を使用した O(N^2) です:-

これは O(N^2) 解ですが、これをさらに縮小するか、O(NlogN) または O(Nlog^2N) で解くための任意のアルゴリズムを使用できますか?

参考までに、ここに何かを見つけました：

2 つの数値を含む最長増加部分列 (LIS)

私の場合は 2 番目の回答の方が適していますが、それをどのように実装できますか?

より良い答えまたはアルゴリズムが必要です。

私は Python プログラミングの初心者であり、次の問題を何時間も解決できませんでした。4行を含むサンプルファイルがあります。ファイル行で見つかるまでにユーザーから2つの入力を取得したいのですが、ループがすべての行を反復していないようです.これはファイルの内容であり、要素はスペースで区切られています:

そして、これは私のコードです:

たとえば、Google と Microsoft を入力して、次の出力を得たいと考えています。

2 つのリストとして。ただし、私のコードは最初の行のみを検出し、他の行は検出しません。他の行を反復しない理由を教えてください。これを修正する方法は？前もって感謝します！

配列内の LIS (最長増加部分列) の計算は、非常に有名な動的計画法の問題です。ただし、すべてのチュートリアルでは、最初に DP の概念を使用せずに再帰的なソリューションを示し、次にボトムアップ DP (反復ソリューション) を適用して解決します。

私の質問は：

再帰的なソリューション自体で メモ化をどのように使用しますか。ただのメモ化ではなく、一次元配列を使ったメモ化。

いくつかの調査を行いましたが、関連するものは何も見つかりませんでした。再帰的なメモ化について質問された箇所は1 & 2の2 箇所ありますが、そちらの解決策はメモ化に 2D Map / Array を使用しています。

とにかく、1D配列でソリューションをメモすると、間違った出力が得られます。これが私がしたことです：

このソリューションが間違った出力を与える理由はわかっていますが、次のようになります。

以前の値に基づいて、与えられたインデックスに対して複数のソリューションが存在する可能性があります。

しかし、1D配列を使用してそれを行う方法を知りたいです。

すべての DPのトップダウンソリューションをボトムアップに、またはその逆に再構成できることを読んだので、ソリューションを知りたいと思っています。

誰かが同じことについて何らかの洞察を提供できれば、非常に役に立ちます。

前もって感謝します。

再帰について学んでいます。例として、配列を与えるアルゴリズム LIS (最長増加部分列) を取り上げました。

次のようになる最長増加サブシーケンスを見つけます。

操作のアイデアから始めるために、私はグーグルで検索していましたが、その機能を見つけました:

示された結果を得るために、私の例でその関数を呼び出すにはどうすればよいですか?