1143. Longest Common Subsequence

DP

출처: https://leetcode.com/problems/longest-common-subsequence/discuss/348884/C%2B%2B-with-picture-O(nm)

위와 같은 어레이를 만들어서 가장 끝에 위치한 값이 답이 될것이다.

예를들어, dp[2][3]이 의미하는 것은 "ac"와 "ab"의 LCS이다.
위 테이블에서 dp[2][3]=1 이 나오는 이유는 a 하나만 공통이기 때문이다.

1. base case는 제일 위 row, 왼쪽 column이다.이 패딩을 만들기위해 string 제일앞쪽에 각각 쓰레기값(#)을 넣어주고 시작한다.

인덱스 실수를 하지않기 위함이다.

t1 = "#"+t1;
t2 = "#"+t2;

2. dp를 순회하면서, 마지막 char이 같은 경우와 다른경우를 구분하여 저장해준다.

• 같은경우: "ac", "abc"

  • c는 서로 같기 때문에, "a"와 "ab" 결과에 1이 추가되는 것과 같다. 이때에는 "a"와 "ab"의 LCS가 1이므로 2가 dp에 저장된다.

• 다른경우: "ac", "ab"

  • c-b가 다르기 때문에, "a"와 "ab", "ac"와 "a" 중 더 큰값을 dp에 저장한다.
  • 왜냐하면 새로 추가된 마지막문자가 다르기 때문에, 이전 LCS에 길이를 추가할 수 없고, 이전에 만들어진 결과 중 가장 큰 결과를 가져와서 LCS를 저장해야하기 때문이다.
    • "c"가 추가되기 이전인 "a"-"ab" 결과 1
    • "b"가 추가되기 이전인 "ac"-"a" 결과 1

Time, Space

이렇게 dp테이블을 모두 채우면 time O(N^2), space O(N^2)에 수행할 수 있다.

var longestCommonSubsequence = function(t1, t2) {
    if(t1===t2) return t1.length;
    
    t1 = "#"+t1;
    t2 = "#"+t2;
    const dp=[...Array(t1.length)].map(row => Array(t2.length).fill(0));
    
    for(let i=1; i<t1.length; i++){
        for(let j=1; j<t2.length; j++){
            if(t1[i]===t2[j]){
                dp[i][j] = 1 + dp[i-1][j-1];
            }else{
                dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j]);
            }
        }
    }
    
    return dp[t1.length-1][t2.length-1];
};

---

https://leetcode.com/problems/longest-common-subsequence/discuss/351689/JavaPython-3-Two-DP-codes-of-O(mn)-and-O(min(m-n))-spaces-w-picture-and-analysis

Discuss에서 본 마음따뜻한 댓글 ㅠ
space 최적화를 하셨던데.. 일단 머리아파서 안보긴했는데.. 언젠간 보고싶다.. ^-^..