就是dp，但是仍然是o(n^2)的，咋办呢？前缀和，这样就O(n)了，轻松AC。
贴个代码给你吧，简单的不要不要的。 
#include <iostream>

using namespace std;

#define pb push_back
#define mp make_pair
#define ll long long
#define ull unsigned ll
#define db double
#define INF 0x3f3f3f3f
#define MOD 1000000007
#define PII pair<int, int>

db dp[100010];
db pfs[100010];

int main() {
    int n;
    cin >> n;
    dp[0] = 0.0f;
    dp[1] = 1.0f;
    dp[2] = 1.0f;
    pfs[0] = 0.0f;
    pfs[1] = 1.0f;
    pfs[2] = 2.0f;
    for (int i = 3; i <= n; i++) {
        dp[i] = 1.0 + 2.0 * pfs[i - 2] / (db)i;
        pfs[i] = pfs[i - 1] + dp[i];
    }
    printf("%.10f\n", dp[n]);
}