We can solve this problem using standard DP or greedy algorithm, based on two observations.

- if n%k == 0, we can copy n/k and paste k-1 times, so dp[n] = min (dp[n/k]+k, for all valid k);
- if k is not a prime number, k = a
*b, we can copy n/k and paste a-1 times, then copy n/b and copy b-1 times, the total is dp[n/k]+a+b. Because a+b is always <= a*b, by induction the answer is the sum of all prime number factors of n;

Standard DP memorization solution, 3 ms, O(n*sqrt(n))

```
class Solution {
public:
int minSteps(int n) {
if (n == 1) return 0;
vector<int> dp(n+1, 0);
dp[2] = 2;
return helper(dp, n);
}
private:
int helper(vector<int>& dp, int k) {
if (dp[k]) return dp[k];
int ans = k;
for (int i = 2; i <= sqrt(k); i++) {
if (k%i == 0) {
ans = min(ans, helper(dp, i)+k/i);
ans = min(ans, helper(dp, k/i)+i);
}
}
dp[k] = ans;
return ans;
}
};
```

Greedy, 3 ms, O(sqrt(n))

```
class Solution {
public:
int minSteps(int n) {
int ans = 0;
for (int i = 2; i <= sqrt(n); i++) {
while (n%i == 0) {
ans += i;
n /= i;
}
}
if (n > 1) ans += n;
return ans;
}
};
```