DP

matrixChain(i, j)
{
for i ← 1 to n
m[i, i] ← 0; //m이라는 2차원 배열(n*m)
for r ← 1 to n-1 ▷ 문제의 크기 = r=n
for i ← 1 to n-r {
j ← i+r;
m[i j] i, ← min {m[i, k] + m[k+1, j] + pi-1pkpj};
}
return m[1, n];//맨마지막에return하는값
}

Xm=<x1,x2...Xm>    LCS Xm-1= Yn-1=> Zk-1
Yn=<y1,y2...Yn>
Zk=<z1.z2,///Zk>


xm= yn이면Xm과 Yn의 LCS의 길이는 Xm-1과 Yn-1의 LCS의 길이보다
1이 크다  ->이건알아두삼

xm≠ yn이면 Xm과 Yn의 LCS의 길이는 Xm과 Yn-1의 LCS의 길이와 Xm-
1과Yn의 LCS의 길이 중큰 것과 같다










LCS(m, n)
▷ 두 문자열 Xm과 Yn의 LCS 길이 구하기
{
for i ← 0 to m
C[i, 0] ← 0;
for j ← 0 to n
C[0, j] ← 0;
for i ← 1 to m
for j ← 1 to n
if (xm= yn) then C[i, j] ← C[i-1, j-1] + 1;
else C[i, j] ← max(C[i-1, j], C[i, j-1]);
return C[m, n];
}








#include <iostream>
#include <string>
using namespace std;
//starcat->문자열붙이는함수
#define max(a,b) (((a)>(b))?(a):(b))

int charCnt(char charPtr[]);
int LCS(int m, int n, char x[], char y[]);

int main(){
int m,n;
char xString[20], yString[20];
char X[20]="0";
char Y[20]="0";

//입력
cout<<"문자열 xm입력=";
cin>>xString;
cout<<"문자열 yn입력=";
cin>>yString;

strcat(X,xString);

m=charCnt(X);

strcat(Y,yString);

n=charCnt(Y);

 

cout<<"LCS길이:"<<LCS(m,n,X,Y);

system("PAUSE");
return 0;

}

 

//CharCnt함수 내부 문자열을 받았을때
int charCnt(char charPtr[]){
int count=0;
while(charPtr[count]!='\0')
count++;

return count;
}

int LCS(int m, int n, char x[], char y[]){

int **C;

C=new int*[m+1];
for(int i=0;i<=m;i++)
 C[i]=new int[n+1];

for(int i=0;i<m;i++)
 C[i][0]=0;
 for(int j=0;j<n;j++)
  C[0][j]=0;

  for(int i=1;i<=m;i++)
   for(int j=1;j<=n;j++)
    
   if(x[i] == y[j]&&x[i]!='\0'&&y[j]!='\0')
    C[i][j] = C[i-1][j-1]+1;
   else C[i][j] = max(C[i-1][j],C[i][j-1]);
        
       
  

 

 

 return C[m][n];
}