Dynamic Programming with Longest Increasing Subsequence(LIS)

1週間以上前にRosalindのLongest Increasing Subsequence問題を考えた後、YouTubeアルゴリズムで推奨Reducibleの動画を整理しました
ダイナミックプログラムの事故過程は以下の5つの方面をまとめた.

Visualize Example

Find an appropriate subproblem

Find relationship among subproblems

Generalize the relationship

Implement by solving subproblems in order

このダイナミックプログラミング構想をLIS問題に使用する:
たとえば、次のシーケンスがあるとします.
[ 8, 2, 1, 6, 5, 7, 4, 3, 9]
このシーケンスの中で最も長いサブシーケンスの長さを求めることに問題をまとめると、動的思考が適用されます.

Visualize Example.

ちょっと複雑ですが、上の図形で表すことができます.この図では、一番後ろのindexから一番長いシーケンスを見つけることができます.

Find an Appropriate Subproblem

すべての増分されたサブシーケンスは、シーケンス全体のサブセットであり、シーケンスには常に開始と終了があります.したがって,LIS関数を用いてサブ問題を定義することができる.
LIS[k]=LIS ending at index kLIS[k] = LIS\space ending\space at\space index\space kLIS[k]=LIS ending at index k
LIS[k]を定義する場合、上記の問題のLIS[3]=2になります.

Find Relationship among Subproblems

サブ問題が定義されている場合は、サブ問題間の関係を見つける必要があります.
上の数列に基づいてサブ問題を定義します.
LIS[0] = 1
LIS[1] = 1
LIS[2] = 1
LIS[3] = 2
したがって、LIS[4]は自分よりも小さな問題の最大値+1となる.
LIS[4]=1+max{LIS[0],LIS[1],LIS[2],LIS[3]}LIS[4] = 1 + max\{LIS[0], LIS[1], LIS[2], LIS[3]\}LIS[4]=1+max{LIS[0],LIS[1],LIS[2],LIS[3]}

Generalize the Relationship

上記の方法でルールが見つかった場合は、シーケンス全体に適用するように正規化します.
LIS[n]=1+max{LIS[k]∣k

Implement by Solving Subproblems in Order

def LIS(A):
	L = [1] * len(A)
	for i in range(1, len(L)):
		subproblems = [L[k] for k in range(i) if A[k] < A[i]]
		L[i] = 1 + max(subproblems, default=0)
	return max(L, default=0)

実施する.
この方法でRossalindの問題を解答、整理、アップロードします.DeBrujin Graphもアップロードするものを整理しなければなりませんが時間がありませんううう