동적 프로그래밍 재귀 또는 반복

Question

동적 프로그래밍에 대해 읽었으며 매우 익숙했습니다. 동적 프로그래밍을 "반복적"및 "재귀 적"방식으로 적용 할 수 있는지 또는 그 중 하나만을 적용하는 것이 우수 사례인지 알고 싶습니다. 좋은 예제/링크가 도움이 될 것입니다.

Answer 1

예, DP를 둘 다 적용 할 수 있습니다.

여기에서 시작

: 그럼 당신은 연습 문제 (이 문제의 각도 Editorial 아이디어를 설명해야 TopCoder.com 당신은 링크를 찾을 수 있습니다, Dynamic Programming: From novice to advanced 첫 번째 튜토리얼

A Tutorial on Dynamic Programming이 http://en.wikipedia.org/wiki/Dynamic_programming

용액 뒤에.

Answer 2

동적 프로그래밍 역방향 구현 재귀 솔루션 (대부분의 경우)을 알 수있다.

N 구두로, 재귀에서 n=0 (또는 다른 값)에 대한 일부 중지 조건이있는 x(n+1) = f(x(n))을 계산합니다.

많은 경우에 기능 f은 일부 최소/최대 기능이지만 반드시 그럴 필요는 없습니다. 또한이 함수는 단일 변수를 사용할 필요가 없습니다.

동적 프로그래밍은 하나 개 이상의 변수가 다음, f(1) 후, f(2) 등

을 f(0)를 계산함으로써이 문제를 해결하는 것이고, 일반적으로 함수를 계산하기 위해 몇몇 천연있을 것이다.

동적 프로그래밍으로 해결할 수있는 예 : 3 개의 골프 클럽이 제공됩니다. 각 골프 클럽은 거리 x 단위의 골프 공을 보낼 수 있습니다 (예 : 24, 37 및 54 단위). 문제는 정확히 200 유닛 떨어져있는 구멍에 충돌 할 수 있습니까? 가능한 경우 최소 촬영 횟수는 얼마입니까? n이 0 인 경우 기능 shot(n) 반환, 몇 가지 큰 수는 n이 0보다 작은 경우 0이 사소한 구현을 허용 할

shots(200) = min(shots(200-24),shots(200-37),shots(200-54)) 

, 및 표현 :

재귀 솔루션은 다음과 같을 것 그렇지 않으면 위에.

그러나 n의 값이 크면 위 식의 다른 분기에서 동일한 값을 반복해서 지정해야합니다. 이 경우 0에서 시작하여 shots(0), shots(1), shots(2) 등을 계산하는 것이 좋습니다. 지수 시간 대신 선형 시간 및 상수 공간을 사용하여이 문제에 대한 "동적 프로그래밍"솔루션이 될 것입니다 (3 방향 트리를 가로 지르는 것).) 및 선형 공간 (호출 스택의 경우)이 있습니다.