前言
新的一年，好好学习。
正文
问题来源
本问题来自leetcode上的640题。
问题描述
最初在一个记事本上只有一个字符 ‘A’。你每次可以对这个记事本进行两种操作：
Copy All (复制全部) : 你可以复制这个记事本中的所有字符(部分的复制是不允许的)。 Paste (粘贴) : 你可以粘贴你上一次复制的字符。 给定一个数字 n 。你需要使用最少的操作次数，在记事本中打印出恰好 n 个 ‘A’。输出能够打印出 n 个 ‘A’ 的最少操作次数。
示例 1：
输入: 3
输出: 3
解释:
最初, 我们只有一个字符 'A'。
第 1 步, 我们使用 Copy All 操作。
第 2 步, 我们使用 Paste 操作来获得 'AA'。
第 3 步, 我们使用 Paste 操作来获得 'AAA'。
分析：
素数因子之和即为所求 非递归解法
func minSteps(n int) int {
ans := 0
for i := 2; i < n/2; i++ {
for n % i == 0 {
ans += i
n = n / i
}
}
if n != 1 {
ans += n
}
return ans
}
递归解法
func minSteps(n int) int {
if n == 1 {
return 0
}
for i := 2; i*i <= n; i++ {
if n%i == 0 {
return minSteps(i) + minSteps(n/i)
}
}
return n
}
为了分析这段递归版本代码，我们可以把代码改写成这样
func minSteps(n, level int) int {
if n == 1 {
return 0
}
for i := 2; i*i <= n; i++ {
if n%i == 0 {
fmt.Println("n : ", n, " i : ", i)
return minSteps(i, level+1) + minSteps(n/i, level+1)
}
}
fmt.Println(level, "---------", n)
return n
}
要注意的是return语句，这里进入if分支后就会退出，所以不会出现多算的情况。还有minSteps(i, level+1)语句可以直接用i来代替。
总结：
勤思考。
结语
不管怎么样好好加油。
