与えられたCのケースとDの許容されるフロアの最大床数

Question

この質問は「プログラミングのインタビューの要素」からのもので、数日間私を困惑させました。

質問には、「CケースとD許容ドロップを考慮すると、最悪ケースでテストできるフロアの最大数はいくらですか？

仮定は以下の通りである：

1）全てのケースが同じ特性を有し、レベルからの1つ破損した場合、そうであろう他のすべて

2）落下を存続する場合は、再び使用されるが、破壊されてもよいです1つは破棄されます

3）落下時にケースが破損した場合、上の床から落下した場合にケースが破損します。それが生き残れば、それはより短い秋に生き残るだろう。

私には、この質問は、滴の数を最小限に抑えようとしている「一般化された2つの卵の問題」の変形のようです。 この問題は、決められた数のドロップがある場合、フロアの数を最大限にしようとします。

溶液で与えられる再帰関係は、以下である： - + 1 + F

F（C + 1、D）= F（1 C、D）（C + 1、D - 1）

ここで、F（c、d）= max＃floorは、w/cケースとd dropsをテストできます。 この繰り返しの関係は、フロアF（c、d - 1）+ 1でテストしたときにケースが壊れない場合、右の項がフロアであるという本の説明にもかかわらず、私を混乱させています。ケースが壊れたときの原因は何ですか？これは反復関係には現れません。

質問には、O（c）スペースで同じ問題を解決する追加質問があります。上記の漸化関係を実装することは、当然、2Dメモマトリックスを用いた動的プログラミングにつながる。あなたは1Dアレイでこれをどうやって行いますか？

Answer 1

1Dアレイでこれをどうしますか？

1.rewriteへの関数：F（C、D）= F（C - 1、D - 1）+ 1 + F（C、D - 1）

2.writeコードとしてこの：

for (i=1; i<=D; i++) 
for (j=C; j>=0; j--) 
    a[j] = a[j-1] + a[j] + 1 

説明：

a[j](after assignment, a[j] equals F(c, d)) 
    = a[j-1](F(c-1, d-1)) + a[j](F(c, d-1)) + 1 

---

マイconfusioケースが壊れたときの原因は何ですか？

フロアxでのテストケースを：

1. 場合が生き残った場合、あなたは、（式中1 + F(c + 1, d - 1)対応）[X + 1、1]の場合は、床の上に壊れることはない知っています。
2. ケースが壊れた場合、ケースは常に床[1、x]で壊れていることがわかります。あなたが1少ないケースを持って