問題：
整数 n と k が与えられ、 が与えられた場合、偏ったコインを個別に無作為に投げたときに正確に表が出る確率を求めます。ここで、pi はi番目のコインが表になる確率です。このタスクの O(n 2 ) アルゴリズムを与えてください。[0, 1] の 2 つの数値を O(1) 時間で乗算および加算できるとします。
p1,p2,..., pn; where pi ε [0, 1]kn
コード化できるように、誰かが再帰関係の開発を手伝ってくれませんか。(質問は、本「Dasguptaによるアルゴリズム」の動的プログラミングの章の演習から来ています)
(n-1) 枚のコインを一緒に投げ、n 枚目のコインをばらばらに投げる状況を考え、相互の独立性を考慮します。
より単純なケースの確率を組み合わせて P(1..n, k) を取得します (ここで、P(1..n, k) は、n 枚のコインで正確に k 枚の表が得られる確率です)
次に、このルールを適用して、NxK テーブルのすべてのセルを埋めます
編集：
n 個のコインで正確に k 個の表を得るには、2 つの方法があります。
a) (n-1) 個のコインが k 個の表を持ち、N 番目のコインが裏である場合、および
b) (n-1) 個のコインに k-1 個の表があり、N 番目のコインが表である場合
それで
P(n, k) = P(n-1, k) * (1 - p[n]) + P(n-1, k-1) * p[n]