無法理解一個DP的解決方案

Question

的問題如下：

拉澤標籤由一個羣戲，你在哪裏整場比賽期間指派子彈（俗稱激光槍）的固定數量。每個對目標敵人進行正確的射擊都會給你一分。

考慮一下可以用「x」和「o」形式表示的一系列命中和未命中，其中「o」代表命中，「x」代表未命中。假設這個系列的形式是「xxxoooxxxxooxxo」，那麼你的最終分數將等於3^2 + 2^2 +1^2，即加起來在整個遊戲中每個最大連續命中數的平方。

正確擊中第j張照片（1≤j≤n）的概率是P（j）。用簡單的術語來說，在第j輪中獲得「o」的概率是P（j）。你需要在你的回合結束時計算預期的分數。

我可以理解這種使用記憶的O（n^2）解決方案，但問題需要O（n）解決方案。我已經看到了O（n）解決方案，但我無法理解它。 O（n）解決方案如下：

for(i = 1; i <= n; i++) 
    dp[i] = (dp[i-1] + p[i-1]) * p[i]; 
for(i = 1; i <= n; i++) 
    ans+=2 * dp[i] + p[i]; 

其中p [i]是擊中第i個目標的概率。任何人都可以解釋O（n）解決方案的工作原理嗎？

Answer 1

可以通過以下方式認爲得分：

1. 每1點擊
2. 2分長度的命中每次運行> 1（計分重疊運行多次）

例如，xxooox的序列將比分：

1. 1爲每個鄰的
01的
2. 2爲OOO
3. 2爲第一OO
4. 2爲二OO

分數= 1 * 3 + 2 * 3 = 3 + 6 = 9分。 （這與匹配原始分數的方式相同，因爲9 = 3 * 3）

dp [i]計算結束於位置i的期望長度> 1的遊程數。

因此，要計算總預期分數，我們需要總和2 * dp [i]（因爲我們每次獲得2分），加上p [i]的總和以增加獲得1分的預期分數每一擊。

的遞推關係是因爲長度> 1的位置結束運行的預期數量，我將是：

1. +1，如果我們有開始我的位置由我得到命中一個新的運行和如果我們通過獲得另一次命中（概率p [i]）繼續在位置i-1結束的運行，則i-1（概率p [i] * p [i-1]）
2. + dp [i-1]