0

これは宿題の質問であり、動的プログラミングのアプローチを使用して解決する必要があります。

私がこれまでにできたことは、次のとおりです。

f(x) が、x が記述できる回数を表すとします。

次に、f(x) = f(x - 1) + 1 です。f(5) = f(4) + 1 (5 = 4 + 1)

しかし、私はこれが正しいアプローチだとは思いません。誰でも助けたいですか？

問題が実際に何であるかの例:

書ける方法の数 4:

4: 3 + 1
4: (2 + 1) + 1
4: 2 + 2
4: (1 + 1) + (1 + 1)
4

1 に答える 1

2

この表現は call partitionです。さまざまな方法で解決できます。

たとえば、

f(x, m) - number of partitions of x 
such that the largest number in that partition is m

それから

f(x, m) = sum of all f(x - m, k) where (1 <= k <= m),
also (k<=x-m), because f(x, y) = 0 where (y > x)

あなたの例では（パーティションの数自体も数えましょう（f（x、x）= 1））

f(1, 1) = 1
f(2, 1) = f(1, 1) = 1
f(2, 2) = 1
f(3, 1) = f(2, 1) = 1
f(3, 2) = f(1, 1) = 1 //+ f(1, 2) zero
f(4, 1) = f(3, 1) = 1 
f(4, 2) = f(2, 1) + f(2, 2) = 2
f(4, 3) = f(1, 1) = 1 // + f(1, 2) + f(1, 3) zeroes
f(4, 4) = 1

したがって、f(4, 1)、f(4, 2)、f(4, 3)、f(4, 4) = 5 の合計 (4 自体をパーティションと見なさない場合は 4)

于 2015-05-18T05:04:19.957 に答える