동적 계획 (1): 기본 적 인 사고 와 절차

기본 사상
동적 계획 은 가장 좋 은 문 제 를 해결 하 는 알고리즘 으로 그 핵심 은 한 문 제 를 여러 개의 키 문제 (여기 서 다음 과 같은 하위 문제 의 사용 조건) 로 분해 하 는 것 이다. 일 부 는 분 치 와 유사 한 사상 (참고 하여 순 서 를 매 길 수 있 는 지 모 르 겠 음) 을 통 해 모든 최 적 화 된 결정 을 통 해 최 적 화 된 해 를 얻 을 수 있다.여기 서 가장 중요 한 것 은 하위 문제 의 사상 이다.

         DP        （          ）     （          ），        ，                          ，                             ，              

검색 을 배 운 후에 가장 간단 한 입문 DP 방법 은 바로 기억 어 검색 입 니 다. 그러나 나중에 대부분의 DP 문 제 는 시간 과 메모리 의 제한 으로 인해 재 귀 를 사용 할 수 없습니다 (함수 의 재 귀 호출 은 스 택 메모 리 를 사용 합 니 다. 또한 함수 의 재 귀 호출 도 많은 시간 을 차지 합 니 다).
하위 문제 해결 법의 적용 조건
세 가 지 를 동시에 만족 시 켜 야 한다.
1. 똑 같은 서브 문 제 를 가진다. 우 리 는 우리 가 분 단 된 서브 문제 도 똑 같은 방법 으로 더 작은 자체 문제 로 나 눌 수 있 고 이런 자체 문제 의 최종 분할 상황 은 해결 할 수 있다 는 것 을 보증 해 야 한다.
2. 최 적 화 된 서브 구 조 를 만족시킨다. 즉, 결정 하 는 서브 결정 도 최 적 화 된 것 이다.
3. 무 후 효성: 이것 은 DP 에서 가장 중요 한 부분 이다. 그 는 모든 하위 문제 의 결정 이 뒤에 해결 되 지 않 은 다른 문제 에 영향 을 주지 못 하고 발생 하면 결정 의 최 우수 성 을 보장 하지 못 한다 고 요구한다. 이것 이 바로 무 후 효성 이다.종종 우리 가 적당 한 상 태 를 찾 아야 한다.이것 은 매우 중요 합 니 다. 이것 은 매우 중요 합 니 다. 이것 은 매우 중요 합 니 다. 예 를 들 어 우 리 는 LIS 에서 앞의 M 항목 의 LIS 를 먼저 구 한 다음 에 차례대로 뒤로 구 합 니 다. str. len 까지 이것 은 바로 우리 가 앞의 M 항목 을 구 하 는 과정 에서 (M + 1) → (str. len) 에 영향 을 주지 않 기 때 문 입 니 다.후 효성 을 없 애 는 예 등 은 블 로 그 를 따로 열 어 말한다.
상용 문제 풀이 절차
이틀 전에 큰 소 에 게 DP 를 학 대 받 은 적 이 있 습 니 다.
STEP 1: 하위 문 제 를 확인한다.이 단계 에서 중요 한 것 은 그 변 수 는 문제 의 규모 가 작 아 지면 서 작 아 지 는 것 이 고 그 변 수 는 문제 의 규모 와 무관 하 다 는 것 을 분석 하 는 것 이다.두 번 째 단계: 상 태 를 확인한다. 위 에서 찾 은 하위 문제 에 따라 분 단 된 하위 문제 의 한정 상 태 를 준다. 세 번 째 단계: 상태 전이 방정식 을 밀어 낸다. 여기 서 당신 의 상태 전이 방정식 이 모든 조건 을 만족 시 키 는 지 주의해 야 한다. 빠 뜨리 지 않도록 주의해 야 한다.네 번 째 단계: 경계 조건 을 확정 합 니 다. 먼저 문제 의 제한 조건 에 따라 문제 에서 제시 한 경계 조건 이 직접 유도 할 수 있 는 지 확인 합 니 다. 만약 에 안 되면 경계 조건 에서 반추 (예 를 들 어 a (n) → a (2) 는 전달 관계 가 있 지만 a (2) → a (1) 가 상기 전달 관계 에 부합 되 지 않 으 면 우 리 는 a (1) 로 a (2) 를 거꾸로 내 놓 는 것 을 고려 할 수 있 습 니 다.그리고 배달 의 종점 을 a (2) 로 설정 합 니 다.다섯 번 째 단계: 실현 방식 을 확인한다. 이것 은 개인 습관 에 따라 01 가방 의 2 층 for 순환 순서 와 같다. 여섯 번 째 단계: 최적화 방법 을 확인한다. 여기까지 왔 을 때 첫 번 째 단계 로 돌아 가 야 한 다 는 것 을 알 게 될 때 가 많다.우선 내 림 차원 문제 (메모리 최적화), 우선 대기 열, 사각형 부등식 (최적화 시간) 등 을 고려한다.
상용 방법
다음은 방법 이지 만 여기에 국한 되 지 마 세 요. 방법 은 무한 합 니 다.
(1) 모델 매 칭 법: LIS, LCS, 01 가방, 완전 가방, 구간 모형, 나무 모형 을 능숙 하 게 기억 하고 이해 합 니 다.기본적으로 원래 모델 을 변화 시 킨 후에 적용 하 는 것 이다.
(2) 세 가지 요소 법: · · · · · · · · 먼저 단 계 를 확정한다. 예 를 들 어 탑 문 제 는 현재 선택 한 것 이 몇 층 인지 먼저 확정한다.상태 확인: 이것 은 가장 자주 사용 하 는 절대 다수의 DP 가 이렇게 하 는 것 입 니 다.먼저 결정: 가방 문제 (i 종 아 이 템 을 선택 하 느 냐 안 선택 하 느 냐) 는 경험 문제 이지 만 저 는 아직 이런 경험 이 없습니다.
(3) 규칙 법 찾기: 어 렸 을 때 부터 미 루 고 인내심 을 가지 고 규칙 을 찾 거나 현지에서 폭력 으로 시 계 를 칠 수 있 습 니 다. 폭력 은 기적 을 일 으 킬 수 있 습 니 다. 2, 3 페이지 를 치지 않 으 면 시 계 를 치 는 것 이 아니 라 몇 년 동안 성 경 기 는 철저하게 깨 달 았 습 니 다. 아무 말 도 하고 싶 지 않 습 니 다.
(4) 경계 조건 법: 일반 경계 시 상태 관 계 를 내 보 내기 쉬 운 곳
(5) 제약 조건 법 추가: 이 조항 은 위의 글 의 제거 후 효과 에 대응 하고 앞으로 의 블 로그 에 예제 가 있 을 것 이다.