数値の組み合わせが一義になります

Question

私は最近このインタビューでこれを尋ねられ、完全に困惑しました。私はこのような質問が以前にここで尋ねられたが、誰もこの上に投げ込まれた小さなひねりを扱っていないことを知っている。

数字を指定すると、番号1,2,3だけを使用して追加できるすべての方法を見つけることができます。だから、3の入力に対して、組み合わせは1,1,1と1,2と2,1と3になるので、出力は4になります。私は硬貨の変更アルゴリズムについて知っていますが、それは私にその順列を与えません1,2および2,1。だから私はちょうどコイン変更アルゴリズムを実装してしまったし、順列の部分を得ることができませんでした。誰にもアイデアはありますか？

Answer 1

あるを参照してください

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

問題の分類についての質問に答えるには、私には動的プログラミング問題のように見えます。

は、例えば5のための可能なオプションを取る：それは再帰的な問題だ、次の質問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