古典的な問題を振り返るアルゴリズム：LIS，LCS-（DPカテゴリ）

LIS、最大増分サブシーケンスの説明は以下の通りである。http://blog.csdn.net/sdjzping/article/details/8759870

 1 #include <iostream>

 2 #include <cstdlib>

 3 

 4 using namespace std;

 5 

 6 int LIS(int* arr, int len) {

 7     if (arr == NULL || len < 1) return 0;

 8     int LIS[len] = {0};

 9     int mlen = 0;

10     for (int i=0; i<len; i++) {

11         LIS[i] = 1;

12         for (int j = 0; j < i; j++) {

13             if (arr[j] < arr[i] && LIS[i] < LIS[j] + 1) {

14                 LIS[i] = LIS[j] + 1;

15             }

16         }

17         if (LIS[i] > mlen) {

18             mlen = LIS[i];

19         }

20     }

21     return mlen;

22 }

23 

24 

25 int main() {

26     int arr[] = {1, -1, 2, -3, 4, -5, 6, -7};

27     int len = sizeof(arr) / sizeof(arr[0]);

28     cout<<LIS(arr, len)<<endl;

29     system("pause");

30     return 0;

31 }

 また、nlognの解法は、len 2 val配列が現在のLIS長を記録するときの終端の数字である（可能性がある場合の最小値、例えば、1,3と1,2のように長さ2のLISを構成することができるが、len 2 val[2]=2）。この配列の詳細な説明については、最初に与えられた接続を参照することができ、最初のアルゴリズムの改善は、配列が秩序化されている。二分割検索を使用することができます。すなわち、処理対象値Vよりも大きいか等しい最初のindexをIに設定すると、このVは、必ずlen 2 val[I-1]で終わる長さI-1のシーケンスの後に挿入できます。新しいシーケンスを形成する長さはIであり、したがって、より新しい配列len 2 val[I]=V（更新は、現在の値がVに相当するためです。最初はこの条件に基づいて検索しています。）この検索の過程はSTLのlowerbandで行うことができます。ここで自分はソースに従ってインデックスのバージョンを書いています。STLで返したのは、ローズマリーです。（配列配列配列配列配列配列は要素ポインタであり、比較する時は配列の開始位置を減らさなければなりません。インデックスが得られます。）

 1 int idx_lower_bound(int a[], int begin, int end, int target) {

 2     int count = end - begin;

 3     int first = begin;

 4     while (count > 0) {

 5         int step = count/2;

 6         int idx = first + step;

 7         if (a[idx] < target) {

 8             first = ++idx;

 9             count = count - step - 1;

10         } else {

11             count = step;

12         }

13     }

14 

15     return first;

16 }

17 

18 int LIS_NLOGN(int arr[], int len) {

19     if (arr == NULL || len < 1) {

20         return 0;

21     }

22     int* len2idx = new int[len+1];

23 

24     len2idx[1] = arr[0];

25     int maxlen = 1;

26     for (int i=1; i<len; i++) {

27         char ch = arr[i];

28         int upper = idx_lower_bound(len2idx, 0, maxlen + 1, ch);

29         len2idx[upper] = ch;

30         if (upper > maxlen) {

31             maxlen = upper;

32         }

33     }

34     return maxlen;

35 }

 
LCS、最大共通サブシーケンス

 1 #include <iostream>

 2 #include <cstdlib>

 3 #include <cstring>

 4 

 5 using namespace std;

 6 

 7 int max(int a, int b) {

 8     return a > b ? a : b;

 9 }

10 

11 int LCS(const char* s1, int len1, const char* s2, int len2) {

12     if (s1 == NULL || s2 == NULL || len1 < 1 || len2 < 1) return 0;

13     

14     int dp[len1 + 1][len2 + 1];

15     

16     for (int i=0; i<=len1; i++) {

17         for (int j=0; j<=len2; j++) {

18             dp[i][j] = 0;

19         }

20     }

21     

22     for (int i=1; i<= len1; i++) {

23         for (int j=1; j<=len2; j++) {

24             if (s1[i-1] == s2[j-1]) {

25                 dp[i][j] = dp[i-1][j-1] + 1;

26             } else {

27                 dp[i][j] = max(dp[i-1][j], dp[i][j-1]);

28             }

29         }

30     }

31     for (int i=0; i<=len1; i++) {

32         for (int j=0; j<=len2; j++) {

33             cout<<" "<<dp[i][j];

34         }

35         cout<<endl;

36     }

37     return dp[len1][len2];

38 };

39 

40 int main() {

41     const char* s1 = "helloyyc";

42     const char* s2 = "xellxddc";

43     

44     cout<<LCS(s1, strlen(s1), s2, strlen(s2))<<endl;

45 

46     system("pause");

47     return 0;

48 }