[LeetCode] 1143. Longest Common Subsequence (C++)

문제

 

https://leetcode.com/problems/longest-common-subsequence/

Longest Common Subsequence - LeetCode

 

풀이

 

난이도: Medium 

 

유명한 DP문제.

 

C++ with picture, O(nm) by votrubac 

'

 

text1을 A, text2를 B라고 했을 때

A의 i번째, B의 j번째 알파벳이 동일하다면 적어도 A의 i번째, B의 j번째 이후로는 공통부분 수열(CS)의 길이가 1 이상이 된다.

 

 

이처럼 A의 i번째와 B의 j번째 알파벳이 동일하다면 이후의 범위에는 현재에 +1 한 값이 CS의 값이 된다.

 

이때 문자열 A와 B의 앞에 더미 문자 한 개를 추가해 놓으면 범위 계산 없이 훨씬 편하게 코드를 짤 수 있다.

 

 

그림 및 풀이 참조: C++ with picture, O(nm) by votrubac 

 

 

코드