**🔗 참고 문제** → [<https://www.acmicpc.net/problem/9251>](<https://www.acmicpc.net/problem/9251>)      // 클릭 시 이동

# 📌 LCS(Longest Common Subsequence) -> 최장 공통 부분 수열

1. 부분수열(Subsequence) -> 문자를 건너뛸 수 있음. 순서만 유지
	- ex) "ACAYKP" 에서 "AAKP" 가능 (중간 문자 Skip)
2. 부분문자열(Substring) -> 반드시 연속된 문자
	- ex) "ACAYKP" 에서 "CAY" 는 가능, "AAK" 는 연속이 아니므로 불가능

🎯 문제 유형

• 두 문자열에서 공통으로 만들 수 있는 가장 긴 부분수열 길이

🚮 선입견을 버리자

• 공통 → 투 포인터 쓰자 → ❌
  • 부분수열은 건너뛰기가 가능하므로, 그리디나 투포인터로 풀이하기 어려움
• 문자를 버릴지 선택할지가 매 순간 갈림
  • 모든 선택을 커버하는 DP가 정석 풀이

💭 어떻게 떠올릴까

• 두 문자열/두 수열 + 최장 공통
• 선택지가 매번 2갈래 이상
  • 현재 문자를 함께 사용
  • 한쪽 문자를 스킵하고 진행
• 선택 분기 반복 → DP로 상태 정의

🧾 DP 상태 정의

• dp[i][j]
  • A 문자의 앞 i글자 + B 문자의 앞 j글자 까지의 LCS 길이
• dp[0][*] = dp[*][0] = 0
  • 문자열 길이가 n, m일 때 → 1-based-index 사용
  • int[][] dp = new int[n + 1][m + 1]
• dp는 문자를 버리는 기록이 아닌, 그 지점(접두사)까지의 최장 길이를 저장