[アルゴリズム]動的プログラミングアプリケーション1)最大増分部分数列
15447 ワード
関連する問題
最長増分部数列
最長増分部分の数列は?
最長増加部分数列とは,与えられた数列の中から構成可能な要素を昇順に選択し,最大長を見つけることである.
二分探索を利用するとO(Nlogn)の時間的複雑さがある.
たとえば、カラム{10,20,10,30,20,50}を数えます.
これをarr[]配列に格納し、dp[]配列に動的プログラミング値を格納します.
このときdp[n]は、n番目のインデックスの値を検索したときに発生する可能性のある最長増分部分数列の長さである.
dp[0]={10}:長さ1
dp[1]={10,20}:長さ2
dp[2]={10}:長さ1
dp[3]={10,20,30}:長さ3
dp[4]={10,20}:長さ2
dp[5]={10,20,30,50}:長さ4
したがって,dpが完了すれば,上記の結果が得られるはずである.
アルゴリズム実装
トップに戻る
簡単に考えれば簡単です.
参照するインデックスで以前の場所を検索します.この値より小さい場合は、再帰呼び出しでナビゲートします.static int LIS(int N) {
// 만약 탐색하지 않던 위치의 경우
if(dp[N] == null) {
dp[N] = 1; // 1로 초기화
// N 이전의 노드들을 탐색
for(int i = N - 1; i >= 0; i--) {
// 이전의 노드 중 seq[N]의 값보다 작은 걸 발견했을 경우
if(seq[i] < seq[N]) {
dp[N] = Math.max(dp[N], LIS(i) + 1);
}
}
}
return dp[N];
}
Bottom-UP（繰り返し文）方式
0~N−1までを二重複文で算出するだけで,各要素の値よりも大きい.for(int i = 0; i < N; i++) {
dp[i] = 1;
// 0 ~ i 이전 원소들 탐색
for(int j = 0; j < i; j++) {
// j번째 원소가 i번째 원소보다 작으면서 i번째 dp가 j번째 dp+1 값보다 작은경우
if(seq[j] < seq[i] && dp[i] < dp[j] + 1) {
dp[i] = dp[j] + 1; // j번째 원소의 +1 값이 i번째 dp가 된다.
}
}
}
以上の方法はいずれも時間的複雑度O(N^2)を有する.
まだこの探索を使っていないから!
二分探索方式
この考え方は,いっそ部分数列を構築する過程である.
トップに戻る
簡単に考えれば簡単です.
参照するインデックスで以前の場所を検索します.この値より小さい場合は、再帰呼び出しでナビゲートします.
static int LIS(int N) {
// 만약 탐색하지 않던 위치의 경우
if(dp[N] == null) {
dp[N] = 1; // 1로 초기화
// N 이전의 노드들을 탐색
for(int i = N - 1; i >= 0; i--) {
// 이전의 노드 중 seq[N]의 값보다 작은 걸 발견했을 경우
if(seq[i] < seq[N]) {
dp[N] = Math.max(dp[N], LIS(i) + 1);
}
}
}
return dp[N];
}Bottom-UP（繰り返し文）方式
0~N−1までを二重複文で算出するだけで,各要素の値よりも大きい.
for(int i = 0; i < N; i++) {
dp[i] = 1;
// 0 ~ i 이전 원소들 탐색
for(int j = 0; j < i; j++) {
// j번째 원소가 i번째 원소보다 작으면서 i번째 dp가 j번째 dp+1 값보다 작은경우
if(seq[j] < seq[i] && dp[i] < dp[j] + 1) {
dp[i] = dp[j] + 1; // j번째 원소의 +1 값이 i번째 dp가 된다.
}
}
}まだこの探索を使っていないから!
二分探索方式
この考え方は,いっそ部分数列を構築する過程である.
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int[] seq = new int[N];
int[] LIS = new int[N];
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
for(int i = 0; i < N; i++) {
seq[i] = Integer.parseInt(st.nextToken());
}
LIS[0] = seq[0];
int idx = 1;
for(int i = 1; i < N; i++) {
if(LIS[idx - 1] < seq[i]) {
LIS[idx++] = seq[i];
}
else if(LIS[0] > seq[i]) {
LIS[0] = seq[i];
}
else {
int temp = Arrays.binarySearch(LIS, 0, idx, seq[i]);
LIS[temp < 0 ? -(temp + 1) : temp] = seq[i];
}
}
System.out.println(idx);
}
}Reference
この問題について([アルゴリズム]動的プログラミングアプリケーション1)最大増分部分数列), 我々は、より多くの情報をここで見つけました https://velog.io/@eeheaven/알고리즘-다이나믹프로그래밍-응용-1-최장-증가-부분-수열テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol