AtCoder Educational DP Contest I問題解いてみた

今回の問題

問題文
N個の足場があります。足場には 1,2,…,Nと番号が振られています。各 i(1≤i≤N) について、足場iの高さは hiです。

最初、足場1にカエルがいます。カエルは次の行動を何回か繰り返し、足場 Nまで辿り着こうとしています。

足場iにいるとき、足場i+1 またはi+2 へジャンプする。このとき、ジャンプ先の足場をjとすると、コスト∣hi−hj∣ を支払う。
カエルが足場Nに辿り着くまでに支払うコストの総和の最小値を求めてください。

自分の回答

#include <bits/stdc++.h>
#include <atcoder/dsu>
using namespace std;
using namespace atcoder;
int main() {
    int n;
    cin >> n;
    double plist[n];
    for (int i = 0; i < n; i++) {
        cin >> plist[i];
    }
    double dp[n+1][n+1];
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= n; j++) {
            dp[i][j] = 0;
        }
    }
    dp[0][0] = 1.0;
    for(int i = 1; i <= n; i++) {
        for(int j = 0; j <= i; j++) {
            if(j != 0) {
                dp[i][j]=dp[i-1][j-1]*plist[i-1];
            }
            dp[i][j]+=dp[i-1][j]*(1-plist[i-1]);
        }
    }
    double ans = 0;
    for(int i = (n+1)/2; i <= n; i++) {
        ans += dp[n][i];
    }
    cout << fixed << setprecision(10) << ans << endl;
    return 0;
}

解説

dp[i][j]をi-1枚目までコインを投げた時表がj枚となる確率とする。dp[i][j]はi番目が表が出る確率と裏が出る確率と、これまでのdp値から求めることができる。漸化式は
dp[i][j]=dp[i-1][j-1]plist[i-1]+dp[i-1][j](1-plist[i-1])
のようになる。iなのかi-1なのかが難しい。あと最後の出力の仕方初めて知った。