[DP] 백준 9251 LCS

 

LCS

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#include <string>

#include <vector>

using namespace std;

int main(void)

{

       int LCS_length = 0, max;

       int **table;

       string a, b;

       cin >> a >> b;

       a = "0" + a;

       b = "0" + b;

       int len1, len2;

       len1 = a.length();

       len2 = b.length();

       table = new int*[len2];

       for (int i = 0; i < len2; ++i) {

              table[i] = new int[len1];

       }

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

              table[0][i] = 0; //table에서 첫번째 열 초기화

       }

       for (int i = 1; i < len2; ++i) {

              max = 0;

              table[i][0] = 0;

              for (int j = 1; j < len1; ++j) {

                     if (a[j] == b[i]) {

                           max = table[i - 1][j - 1] + 1;

                           table[i][j] = max;

                     }

                     else {

                           if (table[i][j - 1] > table[i - 1][j])

                                  table[i][j] = table[i][j - 1];

                           else

                                  table[i][j] = table[i - 1][j];

                     }

              }

              if (LCS_length < max)

                     LCS_length = max;

       }

       cout << LCS_length << endl;

       return 0;

}

참고한 곳 

http://twinw.tistory.com/126