問題
ステップとステップについての質問があります：
Aは階段を上り、1階、2階、3階、...と渡ることができるとします。 あるいはm階だとすると、Aがn段の階段を上る方法はいくつありますか？ここで，mとnは正の整数で，m <= n
ステップ問題の簡単な分析を発表し、より良い解決策が存在するかどうかを探ります。
解析
この質問は同等です：
数nについて、nより小さい数の和がnに等しくなるように、これらの数のうちm（m<=n）を超えないようにする方式はいくつあるか ****。
まずm=n
nを1...に分割するオプションはいくつありますか？.nの部分に分割します：
n=2のとき、{2}を1種類、{1*2}を2種類に分けます。
n=3のとき、1種類の{3}、2種類の[1,2]順列、3種類の{1*3}。
n=4のとき、1種類の{4}、2種類の[1,3][2,2]の順列、3種類の[1,1,2]の順列、4種類の{1*4}。
n=5のとき、{5}を1種類、[1,4][2,3]の順列を2種類、[1,1,3][1,2,2]の順列を3種類、[1,1,1,2]の順列を4種類、{1*5}を5種類に分割。
n=6のとき、{6}を1種、[1,5][2,4][3,3]の順列を2種、[1,1,4][1,2,3][2,2,2]の順列を3種、[1,1,1,3][1,1,2,2]の順列を4種、[1,1,1,3][1,1,1,2,2]の順列を5種、1*6の順列を6種に分割。
......
したがって、分割の各ステップは、整数nの順序k分割問題です。
のk番目の項のn番目の行の一般項です。
そうして手に入れることができるのです：
その場合、番組の総数は表記で示されます)
<m<nの場合：
(正確な方法を与えるためにチェックした後、私は推測のこの部分の前のバージョンで過失厳密であることを非常に申し訳ありません。訂正してくれた張錦君（Zhang Jinkun）、顧建（Gu Jian）、その他の学生に感謝します）。
m < n のとき、この問題は次のように記述できます： k は与えられた正の整数を表し、正の整数 n を部分量のみに分割する順序分割の数を表します。この問題は一般化されたフィボナッチ数の定義を満たします：
n<=kのとき。
n>k>=2の場合。
n<=kなので、正の整数nを1,2...kだけを含む部分量に分割する順序の数はnの順序分割の数であり、nの順序分割の数は2です。
そこで、この反復のループバージョンは、以下のwideFibメソッドのように定理に従って記述されます。
要約
以上をまとめると、この問題の一般的な解は、1セグメント関数で記述することができます：
m=nのときの計算量はO(1)
m<nのとき、複雑度はO(nm+n)となり、線形複雑度には達しませんが、より小さな定数次数を持つことがわかります。
ですから、ある程度の最適化は可能です。
代表例
上記の結論を用いて、以下のコードを示します：
//java
static long stepsOfTerrace(int n, int m) {
if (m > n || n < 2)
throw new IllegalArgumentException();
if (m == n)
return (long) Math.pow(2, n - 1);
else if (m > 1)
return wideFib(n , m);
else
return n;
}
static long wideFib(int n, int k) {
long[] steps = new long[n];
for (int i = 1; i <= n - 1; i++) {
if (i <= k) // hk(k) =2^n-1
steps[i] = (int) Math.pow(2, i - 1);
else // この後、一般化されたフィボナッチ計算に続く
for (int j = i - 1; j >= i - k; j--)
steps[i] += steps[j];
}
long sum = 0;
for (int i = n - k; i <= n - 1; i++)
sum += steps[i];
return sum;
}
