前言
数论问题
正文
问题来源
本问题来自leetcode上的650题。可能由于有动态规划这个提醒，一会儿就想出这道题的解法！可是，这并不是最优的解法。
问题描述
最初在一个记事本上只有一个字符 ‘A’。你每次可以对这个记事本进行两种操作： Copy All (复制全部) : 你可以复制这个记事本中的所有字符(部分的复制是不允许的)。 Paste (粘贴) : 你可以粘贴你上一次复制的字符。 给定一个数字 n 。你需要使用最少的操作次数，在记事本中打印出恰好 n 个 ‘A’。输出能够打印出 n 个 ‘A’ 的最少操作次数。
示例 1:
输入: 3
输出: 3
解释:
最初, 我们只有一个字符 'A'。
第 1 步, 我们使用 Copy All 操作。
第 2 步, 我们使用 Paste 操作来获得 'AA'。
第 3 步, 我们使用 Paste 操作来获得 'AAA'。
分析：
若采用动态规划的思想，输入为素数则输出一定为该素数本身，而非素数情况的输出一定小于等于输入本身。则我们可以将 该输入作为默认值。非素数a作为输入时，其值一定和其能满足a%i==0的i值有关。 C代码如下：
#define min(x,y) ((x)<(y)?(x) : (y))
int minSteps(int n) {
int *dp = (int*)malloc(sizeof(int)*(n+1));
int ret;
int i,j;
int temp;
dp[1] = 0;
//dp[2] = 2;
for(i=2;i<=n;i++)
{
temp = i;
for(j=2;j<=i/2;j++)//可优化
{
if(i%j==0)
{
temp = min(temp,dp[j]+i/j);//可优化
}
}
dp[i] = temp;
}
ret = dp[n];
free(dp);
return ret;
}
其中上段代码中标注可以优化，优化思路是j从j=i/2递减，当i%j处即可获得当前dp[i]的最小值，可以进行break操作。
但是这段执行结果只击败了百分之二十几的对手，并非最优解。
官方给出的最优解，如下所示：
int minSteps(int n) {
int res = 0, i = 0;
for(i = 2; i <= n; i++){
while(n % i == 0){
res += i;
n = n / i;
}
}
return res;
}
和动态规划的思想是一致的。 递归版本
int minSteps(int n) {
if (n == 1) return 0;
for (int i = 2; i < n; i++)
if (n % i == 0) return i + minSteps(n / i);
return n;
}
总结：
看出dp[j]+i/j，这个是非常重要的。
结语
还是需要多训练一下动态规划的思维。
