There is only one character 'A' on the screen of a notepad. You can perform one of two operations on this notepad for each step:
Copy All: You can copy all the characters present on the screen (a partial copy is not allowed). Paste: You can paste the characters which are copied last time. Given an integer n, return the minimum number of operations to get the character 'A' exactly n times on the screen.
Example 1:
Input: n = 3
Output: 3
Explanation: Initially, we have one character 'A'.
In step 1, we use Copy All operation.
In step 2, we use Paste operation to get 'AA'.
In step 3, we use Paste operation to get 'AAA'.
Example 2:
Input: n = 1
Output: 0
Constraints:
1 <= n <= 1000
题目设计的很简单，而且很有意思，但递推公式比较难找，我自己ac的思路感觉不是最优解。
思路1:
对于任何一个n，最后一次paste一定不可能大于n/2.但可能等于
比如17，最后一次paste绝对不可能是9，如果是9意味着一定需要当前一定是大于等于9的 二9+9>17
所以只能从1~8的中找。
所以设计一个dp存放i的最优解。
一个map[int]int存放最后一次paste对应的索引。
func minSteps(n int) int {
// key为步长，value为dp的索引，如果步长相等的两个索引q，p，且p>q则存p。也就是存更大的索引。
index := map[int]int{}
dp := make([]int, n+1)
// dp[0]没用
dp[0], dp[1] = 0, 0
index[1] = 1
for i := 2; i <= n; i++ {
maxStep := i / 2
for j := maxStep; j >= 1; j-- {
// k为起始点索引，并且可以用j的步长去paste
k := index[j]
// %j不等于0说明，在k做起始点不能paste出当前的长度i的结果
if (i-k)%j != 0 {
continue
}
// 可以在k做起始点的情况走到,i-k为距离，j为步长，所以加上(i-k)/j次paste
dp[i] = dp[k] + (i-k)/j
// 相等说明需要多一次copy
if j == k {
dp[i] += 1
}
// 更新index
index[j] = i
break
}
index[i] = i
}
//fmt.Printf("%+v", dp)
return dp[n]
}