# C++, O(sqrt(n)), DP and greedy prime number solution

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

1. 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);
2. if k is not a prime number, k = ab, 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 <= ab, 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;
}
};
``````

• Um... I don't think your solution is a DP solution but a recusion solution in fact cause that there is not a iteration operation in your solution.

• @microface The first solution is memoization DP with overlapping subproblems. Try some examples to see, such as n = 16.
The second is a greedy solution, optimized from DP. I am not smart enough to come out with the second solution directly. The first one is my original solution during the contest.

• Amazing greedy algorithm and proof!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.