646. Maximum Length of Pair Chain

646. Maximum Length of Pair Chain

https://leetcode.com/problems/maximum-length-of-pair-chain/

문제

풀이

1. pairs을 내림차순을 정렬한다.
   => pairs = [[7, 8], [4, 5], [1, 2]]
2. 조건에서 -1000 <= lefti < righti <= 1000를 명시하였으므로 dp[0]~dp[2002]를 0으로 초기화한다.(배열 인덱스에서 음수를 양수로 변환하기 위해서 1000을 더함)
3. i = 0일 때 dp[1007] = 1로 초기화 (맨 마지막 수이기 때문) 그리고 prev = 7을 저장
4. i = 1일 때 [4, 5]이고 1005~1006까지 dp[1007]값을 저장한다. 그리고 가능한 경우의 수를 보면 [4, 5]를 포함한 최대 체인 수, [4, 5]를 포함하지 않는 최대 체인 수로 볼 수 있다. 즉
   max(dp[1005], dp[1006] + 1) => max(포함하지 않는 최대 체인 수, 포함한 최대 체인 수) => (1, 2) 즉 dp[1004] = 2가 저장된다. prev = 4저장
5. i = 2일 때 [1, 2]이고 1003~1003까지 dp[1004]값을 저장한다. 마찬가지로 max(dp[1003], dp[1003] + 1) => max(포함하지 않는 최대 체인 수, 포함한 최대 체인 수) => (2, 3) 즉 dp[1004] = 3가 저장된다.

즉 안쪽 for문에서 pairs에 없는 범위들은 그 위에서 계산된 최대값을 저장하고 pairs를 계산할 때에는 해당 pairs[i]가 포함되있을 때, 그렇지 않을 때에 최대값을 저장하고 prev를 갱신해주는 것이다.

결과