[P4550] 收集邮票 - 概率期望,dp

套路性地倒过来考虑，设\(f[i]\)表示拥有了\(i\)种票子时还需要多少次购买，\(g[i]\)表示还需要多少钱
推\(g[i]\)递推式时注意把代价倒过来（反正总数一定，从顺序第\(1\)张开始加钱和倒序没有区别）

#include <bits/stdc++.h>
using namespace std;

const int N = 10005;
double f[N],g[N];
int n;

int main() {
    cin>>n;
    for(int i=n-1;i>=0;--i) {
        f[i]=f[i+1]+1.0*n/(n-i);
    }
    for(int i=n-1;i>=0;--i) {
        g[i]=1.0*i/(n-i)*(f[i]+1)+g[i+1]+f[i+1]+1;
    }
    printf("%.2lf\n",g[0]);
}

[P4550] 收集邮票 - 概率期望,dp

原文：https://www.cnblogs.com/mollnn/p/12248928.html