leetcode 650. 只有两个键的键盘

最初在一个记事本上只有一个字符 'A'。你每次可以对这个记事本进行两种操作：

Copy All (复制全部) : 你可以复制这个记事本中的所有字符(部分的复制是不允许的)。
Paste (粘贴) : 你可以粘贴你上一次复制的字符。
给定一个数字 n 。你需要使用最少的操作次数，在记事本中打印出恰好 n 个 'A'。输出能够打印出 n 个 'A' 的最少操作次数。

思路：动态规划

class Solution {
public:int dp[10001];int minSteps(int n) {dp[1] = 0, dp[2] = 2;for(int i = 3; i<=n; i++){if(i%2 == 0){dp[i] = dp[i/2] + 2;}else{bool flag = false;for(int j = i-1; j>=sqrt(i); j--){if(i%j == 0){ dp[i] = dp[j] + i/j; flag = true; break;} }if(!flag) dp[i] = i; }}return dp[n];}
};

顺便贴下大佬的做法（找n的质数因子然后相加）：

class Solution {
public:int minSteps(int n) {int res = 0;for (int i = 2; i <= n; i++) {while (n % i == 0) {res += i;n /= i;}}return res;}
};