Go, Vantage point
가까운 곳을 걷지 않고 서는 먼 곳을 갈 수 없다.
Github | https://github.com/overnew/
Blog | https://everenew.tistory.com/
티스토리 뷰
반응형
문제
https://leetcode.com/problems/longest-common-subsequence/
Longest Common Subsequence - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
풀이
난이도: Medium
유명한 DP문제.
'
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
코드
반응형
'알고리즘 공부 > LeetCode' 카테고리의 다른 글
| [LeetCode] 377. Combination Sum 4 (C++) (0) | 2021.10.28 |
|---|---|
| [LeetCode] 139. Word Break (C++) (0) | 2021.10.25 |
| [LeetCode] 300. Longest Increasing Subsequence (C++) (0) | 2021.10.23 |
| [LeetCode] 322. Coin Change (C++) (0) | 2021.10.21 |
| [LeetCode] 268. Missing Number (C++) (0) | 2021.10.20 |
댓글