题解 | 1=N

补一个不懂数学的做法，记忆化不记忆化好像都能过

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

const int N = 300010, INF = 0x3f3f3f3f;
int dp[N];

int dfs(int x) {
    int &ans = dp[x];
    if (x <= 1) {
        return dp[x];
    }

    if (ans != INF) {
        return dp[x];
    }

    for (int i = 2; i <= x; i ++) {
        if (x % i == 0) {
            ans = min(ans, dfs(x / i) + i);
        }
    }
    ans = min(ans, x);
    return ans;
}

int main() {
    memset(dp, 0x3f, sizeof dp);

    dp[0] = 0;
    dp[1] = 0;
    int n;
    cin >> n;
    cout << dfs(n) << endl;
}
// 64 位输出请用 printf("%lld")