고지 사항: 아래에 설명된 방법은 보편적이지 않지만 종종 문제를 해결하거나 올바른 솔루션을 찾는 데 도움이 될 수 있습니다.
일부 축(일반적으로 시간 축 또는 일부 배열의 인덱스)에 위치한 일련의 간격이 있고 선택한 간격이 교차하지 않도록 최적의 방법으로 일부를 선택해야 하는 경우 동적 프로그래밍을 사용해야 합니다. .
대략적인 솔루션 체계:
처음에는 사용 가능한 간격을 오른쪽 경계로 정렬합니다. 다음 역학을 시작하겠습니다. dp[i] - 첫 번째 i 간격에 대한 답입니다.
다음과 같이 다시 계산합니다. 먼저 이 간격이 사용되지 않는 상황을 고려한 다음 dp[i] = dp[i-1]만 고려합니다. 이것은 i가 커짐에 따라 dp[i]의 값이 감소하지 않도록 보장합니다. 그리고 이것은 논리적이기 때문입니다. 새로운 격차를 추가한다고 해서 전체적인 답변을 악화시킬 수는 없습니다. 단순히 새로운 격차를 무시하거나 이를 사용하여 더 수익성 있는 변형을 구성합니다. 이제 i번째 간격을 사용하려면 겹치지 않는 간격 세트를 선택해야 하므로 오른쪽 경계가 현재 간격의 왼쪽 경계보다 작은 간격을 사용할 수 있습니다. 이를 위해 처음에는 오른쪽 경계를 기준으로 간격을 정렬하여 이제 필요한 위치를 효율적으로 찾을 수 있습니다. 가능하면 분석적으로 수행할 수 있지만 일반적으로 오른쪽 경계가 현재 경계의 왼쪽 경계보다 작고 동시에 가능한 최대값인 binsearch로 간격을 찾을 수 있습니다. 하나. 우리는 탐욕스러운 이유로 올바른 경계를 최대화하려고 합니다. 내가 성장함에 따라 대답은 증가할 수 밖에 없습니다. 따라서 필요한 위치 p를 찾고 dp[i]를 통해 dp[p]와 i번째 간격을 다시 계산합니다.