내가 조사해서 총결산을 해 보았다.

DP(Dynamic Program)란 무엇입니까?

우선, 봐봐Wikipedia.(참조 섹션이 수정됨)
알고리즘은 상세하게 정의된 것이 아니라 다음과 같은 두 가지 조건을 만족시키는 알고리즘의 총칭이다.
1. 분할 통치법: 일부 문제를 해결하고 그 결과를 이용하여 전체 문제를 해결한다.
2. 필기화: 일부 문제의 계산 결과를 재사용
응, 이것은 분, 기, 두 가지 알고리즘을 포함하는 알고리즘이야.
적용되는 조건이 있는 것 같습니다.
최적화 문제에 응용되는 상황에서 일반적으로 다음과 같은 두 가지 응용 문제를 만족시켜야 한다.
1. 부분 구조의 최적성과 최적성 원리
2. 일부 문제의 중복성

부분 구조 최적화

일부 구조의 최적성은 다음과 같은 두 가지 조건이 성립되는 것을 가리킨다.
ⅰ. 일부 문제도 같은 최적화 문제를 성립시켰다
ⅱ. 일부 문제는 독립적이다
왠지 한자만 있는 게 어려울 것 같아서 그런 것 같아요.


예를 들어 문제를 5단계로 나누어 해결한다.이때 모든 단계의 최적해는 전체 최적해와 일치해야 한다.NG의 예인 단계 2에서는 다른 1(빨강), 단계 3에서는 다른 2(노란색)가 최적이지만, 전체적인 최적은 아니다.이런 성질의 문제는 동적 계획법으로 풀 수 없다.
아마 그럴 것 같아...NG의 예는 뭐가 있을까요?

일부 문제의 중복성

일부 문제의 중복성은 같은 부분의 문제가 중복되는 것을 가리킨다.
만약 이것이 없다면 필기화의 의미는 없어질 것이다.

예제 (피보나치 수열)

다운사이드 방식과 다운사이드 방식은 각각 의심 코드를 게재했다.이거 봤어요.나는 복귀보다 순환이 처리를 생각하기 쉽다고 생각한다.

동적 계획법 을 말하자면, 예제 이다

가방이요.다음에 봐요여기..
피바나치 수열에서 필기화한 시계는 1차원(몇 위)이지만 가방 문제는 2차원(남은 상품*가방의 용량)이어서 좀 복잡하다.하지만 할 일은 문제를 분리한 후 분리법으로 책상을 묻는 것뿐이다.
문제가 좀 크니 그것을 작게 해라.가방의 용량은 5kg이며 상품은 아래 4가지입니다.
ID
무게(kg)
가치 01 명
0
1
3
1
2
2
2
2
1
3
1
2
이번에 채워야 할 책상은 밑의 느낌이 있다.찾아야 할 것은 남은 물건 4, 가방 용량 5kg의 경우 책상으로 하면 가장 오른쪽(0,5)이다.
↓ 아이템/→용량
0
1
2
3
4
5
0
-
-
-
-
-
추구하고 싶은 건 여기예요.
1
-
-
-
-
-
-
2
-
-
-
-
-
-
3
-
-
-
-
-
일단 여기.
가장 먼저 착수한 것은 맨 오른쪽 아래(3,5)에서 천천히 탁자를 매립하는 것이다.
(3,5) 가방의 용량 5에 따라 화물을 넣을지 말지를 결정한다.넣으면 가치가 커지기 때문에 (3,5) 2로 결정됩니다.
↓ 아이템/→용량
0
1
2
3
4
5
0
-
-
-
-
-
추구하고 싶은 건 여기예요.
1
-
-
-
-
-
-
2
-
-
-
-
-
그다음에 여기.
3
-
-
-
여기 필요해.
-
2
이어서 구하다(2,5).이를 위해서는 (3, 5)과 (3, 3)이 필요하다.(3,5)는 물품 2를 넣지 않는 모드, (3,3)는 넣는 모드다.(3,5) 아까 요구한 2.(3,3)와 (3,5)는 같다.(2,5)는 (3,5) 또는 (3,3)에 물품 2의 가치를 더한 큰 쪽이기 때문에 3으로 결정했다.
↓ 아이템/→용량
0
1
2
3
4
5
0
-
-
-
-
-
추구하고 싶은 건 여기예요.
1
-
-
-
-
-
-
2
-
-
-
-
-
3
3
-
-
-
2
-
2
마찬가지로 구(1,5),(0,5)를 통해 최종적으로 원하는 해를 얻는다.
글을 쓰면 이해하기 어렵지만 실제로 책상을 손으로 채우면 이해할 수 있다.이 예는 약간 미묘하지만 필기화도 효과적임을 알 수 있다.
이 프로그램을 프로그램으로 설정하면 위에 열거한 이거. 프로그램이 됩니다.
그렇구나.

문제를 찾아보았다

이것 심플하고 좋은 느낌.책상은 일차원이다.

끝말

이 녀석이 프로콘을 할 때 꼭 나오니까 잘 억제하려고 기사를 썼어요.나는 마지막에 연습을 할 수밖에 없다고 생각한다.힘내세요.