E40 概率DP 求期望

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

double f[1010][1010];
int main()
{
    int n,k;scanf("%d%d",&n,&k);
    f[n][k]=0;
    for(int i=n;i>=0;i--)
        for(int j=k;j>=0;j--)
        {
            if(i==n && j==k) continue;
            double p1,p2,p3,p4;
            p1=1.0* i/n * j/k;
            p2=1.0* i/n *(1.0- 1.0*j/k);
            p3=1.0* (1.0- 1.0*i/n) *j/k;
            p4=1.0* (1.0- 1.0*i/n) *(1.0- 1.0*j/k);
            f[i][j]=(f[i][j+1]*p2+f[i+1][j]*p3+f[i+1][j+1]*p4+1.0)/ (1-p1);
        }
    printf("%.4lf\n",f[0][0]);
    return 0;
}