숫자의 고유 한 조합으로 최대 합계가

Question

최근 인터뷰에서이 질문을 받았으며 완전히 혼란스러워졌습니다. 나는 이것에 대한 질문이 전에 여기에 있었지만 아무도이 것에 던져진 작은 꼬임을 다룰 수는 없다는 것을 안다.

숫자가 주어지면 숫자 1,2,3 만 사용하여 추가 할 수있는 모든 방법을 찾습니다. 그래서 3의 입력에 대해 출력은 4가 될 것입니다. 왜냐하면 조합은 1,1,1과 1,2, 2,1과 3이 될 것이기 때문입니다. 동전 변경 알고리즘에 대해서는 알고 있지만 그 순열을주지는 않습니다. 1,2 및 2,1. 그래서 나는 동전 교환 알고리즘을 구현하고 결국 순열 부분을 얻을 수 없었습니다. 아무도 아이디어가 있니?

Answer 1

입니다 : 예를 들어

테이크 5에 대한 가능한 옵션

X X X X X 
1 X X X X 
2 X X X 
3  X X 

그래서 f(5)=f(4) + f(3) + f(2)

그래서 일반적인 솔루션은

f(1)=1 
f(2)=2 
f(3)=4 
f(N)= f(N-1) + f(N-2) + f(N-3) for N > 3 

입니다

Answer 2

문제의 분류에 대한 질문에 대답하려면 동적 프로그래밍 문제가있는 것 같습니다. stanford.edu에서 여기

1 차원 DP 예

◮ Problem: given n, find the number of different ways to write 
n as the sum of 1, 3, 4 
◮ Example: for n = 5, the answer is 6 
5 = 1 + 1 + 1 + 1 + 1 
= 1 + 1 + 3 
= 1 + 3 + 1 
= 3 + 1 + 1 
= 1 + 4 
= 4 + 1 

그리고 찍은 질문 다음 참조 그것은 재귀 문제 년대 solution to similar problem