使用時

:指定したコンテナ順序を損なわずに昇順に並べた最長のコレクションを作成します.

[3]のインデックスを確認する場合は、前のすべてのインデックスを確認しながら、最も可能なリストを選択するため、二重砲口を使用します.
思い出すべきだ.

関連する問題

金泰元dp最大線接続:旋回のように見えますが、実際にはLIS問題

です.

金泰元最高塔

標準:https://velog.io/@kwt0124/%EB%B0%B1%EC%A4%8011053%EB%B2%88-%EA%B0%80%EC%9E%A5-%EA%B8%B4-%EC%A6%9D%EA%B0%80%ED%95%98%EB%8A%94-%EB%B6%80%EB%B6%84-%EC%88%98%EC%97%B42

伊科泰兵士

配備

クラウド:jmos

毎日忘れてた

https://www.youtube.com/watch?v=YWnOMETo4ww

最も成長した要素を集める

=>絵を描いて、コードで表現すればいい!
1)0番目の値を1に設定する必要があります.
2)最初のインデックス値と0番目のインデックス値を比較すると、dp[1]の値が更新される.
このときmaxを使用して最大値に更新します.
//ダミーコード
for(int i = 1; i < n; i++)
{
for(int j = i; j >= 0; j--)
{
//iは更新するインデックスです
if(v[i] < v[j])
{
d[i] = max(dp[j] + 1, dp[i]);
->このように+1の理由は,以前の値のdp個数の増加に伴い,現在+1個増加しているからである.
:5、3、7、8、6、2、9、4の中で最も長い数列の長さは?

すべての場合の数
5
3

5 - 7
3 - 7
5 - 7 - 8
3 - 7 - 8
3 - 7 - 8 - 9
5 - 7 - 8 - 9
3 - 8 - 9
5 - 8 - 9
3 - 6
5 - 6
~~と表示できます.

そっと

->最大値を探すので、最後の値を無条件に考えることはできません.
=>上図の結果は次のとおりです.
dpテーブルは1/1/2/3/2/1/4/2からなり,最大値は4であった.

てんかしき

:d[index]:indexまでの最長数列の長さ値
d[7]:9は最後の項であり、ここで最も長い数列の長さを表す.

ソース1

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;



//5를 만들수 있는 연속 수열 만들기
int main()
{
	vector<int>v = { 5,3,7,8,6,2,9,4 };
	vector<int>dp(v.size(), 1);

	//1 1 1 1 1 1 1 1 1
	//1 1 
	//1 1 2 
	//1 1 2 3

	for (int i = 1; i < v.size(); i++)
	{
		for (int j = 0; j < i; j++)
		{
			if (v[j] < v[i])
			{
				dp[i] = max(dp[i], dp[j] + 1);
			}
		}
	}



}

ソース2

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;


//위에서 부터 나오게 하자. 
int main(void) 
{
	_CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);
	
	int n;
	cin >> n;

	vector<int >v(n);
	vector<int>dp(n, 1);

	for (int i = 0; i < n; i++)
	{
		cin >> v[i];
	}

	dp[0] = 1;

	for (int i = 1; i < n; i++)
	{
		for (int j = i - 1; j >= 0; j--)
		{
			if (v[j] < v[i])
			{
				dp[i] = max(dp[j] + 1, dp[i]);
			}
		}
	}

	for (int i = 0; i < n; i++)
	{
		cout << dp[i] << " ";
	}

	cout << endl;

	int max_Value = -1;
	for (int i = 0; i < n; i++)
	{
		max_Value = max(dp[i], max_Value);
	}

	cout << "최대 길이는 "<< max_Value << endl;


}

イコタ兵士を配置する

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;




int main()
{
	//전투력이 높은 병사가 앞으로 오도록 해야한다. 내림차순으로 
	//lis 문제이다. 

	int n;
	cin >> n;
	vector<int>v(n, 0);

	for (int i = 0; i < n; i++)
		cin >> v[i];

	//4,2,5,8,4,11,15
//dp :1 1 2 3 2  4 5  
	//4,5,8,11,15

	reverse(v.begin(), v.end());

	vector<int>dp(n, 1);

	for (int i = 1; i < n; i++)
	{
		for (int j = 0; j < i; j++)
		{
			if (v[j] <  v[i])
			{
				dp[i] = max(dp[i], dp[j] + 1);
			}
		}
	}

	int max = 0;
	for (int i = 0; i < n; i++)
	{
		if (max < dp[i])
			max = dp[i];
	}
	cout << n - max;

}