,4 센트, 6 센트, 10 센트로 센트의 우표를 만들 수있는 방법을 찾는 방법은 무엇입니까?
N = 4 (4 × 1 개) 방법
N = 10 (4 × 1, 6x1) (10x1) 2 가지
방법의 수를 표현할 수있는 모든 방정식 있는가
?recurrence-relation 태그를 사용했습니다. 예, 재귀를 사용하여 방법 수를 계산할 수 있습니다.
P(N) = P(N-10) + P(N-6) + P(N-4)
P(0) = 1
설명 - 당신이 등 (N-10) 센트 합계 10 센트 동전을 사용하여, 합계 N을 얻을 수 있습니다. N 값이 너무 큰 경우 반복 알고리즘이 너무 길어 계산을 가속화하는 동적 프로그래밍 알고리즘을 작성할 수 있습니다. (DP는 계산 된 값을 더 작은 합계로 재사용합니다)
교단 목록이 있다고 가정합니다. 귀하의 경우 그것은 A = [4,6,10]입니다. 그래서 당신은 다음과 같은 사항이 있다고 가정 : 우리가 다시 사용하여 하위 문제, DP은 훌륭하게 작동의 가능성을 볼 수있는
# Given the list of denominations, its length and the sum.
P(A,N,K) = 0 if N < 0 or K < 0,
1 if K = 0,
P(A,N-1,K) + P(A,N-1,k-A[N]) #A[N]-> Nth element of list
:
A = [4,6,10]
Length of list A = N
Sum = K
문제
는 다음과 같이 쓸 수 있습니다.
이 질문은 프로그래밍이나 소프트웨어 개발 대신 [math.se]에 관한 것이므로 주제를 벗어나는 것으로 선택합니다. – Pang