최대 공통 하위 시퀀스(LCS 문제)의 DP 해법

어.대학 1학년 때 해봤는데 ACM입문DP문제인데 대학 3학년 때 저는 구체적으로 어떻게 하는지 잊어버렸어요. DP밖에 기억이 안 나요. 면접에서 자주 이 질문을 하기 때문에 알아볼 필요가 있어요.
제목 묘사 약.
문제풀이 사상은 바로 DP이다. DP는 두 가지를 알아야 한다. 하나는 상태가 무엇인지, 다른 하나는 상태 간의 점차적인 관계가 무엇인지.
이 문제는 2차원 DP입니다. 상태 dp[i][j]를 사용하면str1이 i자 (i 포함) 를 얻었고,str2가 j자 (j 포함) 를 찾았을 때 가장 긴 공통 서열의 길이를 나타냅니다.(i, j 값은 1부터 시작)
점진적 관계식은 다음과 같습니다.
dp[i][j] = 0 (i = 0 또는 j = 0)
dp[i][j] = max(
dp[i-1][j-1]+1, (만약str1[i]=str2[j])
dp[i-1][j],
dp[i][j-1]
);
종합하면 가장 긴 공통 서열 길이를 구하는 코드를 쓸 수 있으며 HDU1159로 검증할 수 있다. 이 문제는 LCS 템플릿 문제다.
//아래 코드에 실제 저장된 문자열은 0에서 시작하고 dp수조는 1에서 시작합니다.

#include 
#include 
#include 
#include 
using namespace std;

int dp[1000][1000];

int main(){
    string str1,str2;
    while(cin>>str1>>str2){
        memset(dp, 0, sizeof(dp));
        int m = str1.length();
        int n = str2.length();
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                if(str1[i-1] == str2[j-1]){
                    dp[i][j] = dp[i-1][j-1] + 1;
                }
                dp[i][j] = max(dp[i-1][j], dp[i][j]);
                dp[i][j] = max(dp[i][j-1], dp[i][j]);
            }
        }
        cout<

그리고 필기 면접을 볼 때 이 가장 긴 공공 서열을 출력할 수 있습니다. 제가 사용하는 방법은 구조체를 구축하는 것입니다. 모든 DP 상태에서 이 상태가 어느 상태에서 밀려왔는지, 그리고 이 상태에 새로운 상등 문자가 추가되었는지 보존하는 것입니다.이렇게 하면 dp[m][n]상태에서 이 상태가 처음에 어떤 상태에서 유추되었는지 거슬러 올라갈 수 있고 가장 긴 공공 서열이 무엇인지 알 수 있다.
코드는 다음과 같습니다. 이 코드의 주석 부분에서 출력을 디버깅하여 쉽게 이해할 수 있습니다.

#include 
#include 
#include 
#include 
#include 
using namespace std;

struct NODE{
    int len;
    int preX;
    int preY;
    bool selected;
    NODE(){
        len = 0;
        preX = -1;
        preY = -1;
        selected = false;
    }
    NODE(int l, int x, int y, bool s){
        len = l;
        preX = x;
        preY = y;
        selected = s;
    }
};

NODE dp[1000][1000];
string str1,str2;
int m,n;

void printLCS(){
    cout< st;
    int i = m, j = n;
    while(i!=-1 && j!=-1){
        //cout<>str1>>str2){
        m = str1.length();
        n = str2.length();
        for(int i=0;i<=m;i++){
            for(int j=0;j<=n;j++){
                dp[i][j] = NODE();
            }
        }
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                if(str1[i-1] == str2[j-1]){
                    dp[i][j] = NODE(dp[i-1][j-1].len + 1, i-1, j-1, true);
                    //cout<dp[i][j].len){
                    dp[i][j] = NODE(dp[i-1][j].len, i-1, j, false);
                    //cout<dp[i][j].len){
                    dp[i][j] = NODE(dp[i][j-1].len, i, j-1, false);
                    //cout<