Initially on a notepad only one character 'A' is present. You can perform two operations on this notepad for >each step:
Copy All: You can copy all the characters present on the notepad (partial copy is not allowed).
Paste: You can paste the characters which are copied last time.
Given a number n. You have to get exactly n 'A' on the notepad by performing the minimum number of steps permitted. Output the minimum number of steps to get n 'A'.Example 1:
Input: 3
Output: 3
Explanation:
Intitally, 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'.
Note:
The n will be in the range [1, 1000].
翻譯：略
第一反應就是DP卷雕。
DP第一步要確定含義机杜，一般來說都是直指問題鹰服，也就是說設dp[i]是得到i個A所需要的最少步數(shù)。
那么很明顯就有一個關系：在得到dp[i]的前提下嗦玖，我們可以copy然后paste任意次數(shù)，也就是說
dp[k*i]=dp[i] + k 随常，其中k是大于1的正整數(shù)掩蛤，copy1次paste k-1次。
連續(xù)copy沒有意義干花，所以最優(yōu)的單元操作一定是一個copy加上1到若干個paste妄帘。這個公式就涵蓋了所有最優(yōu)單元操作。
當然DP還要注意方向池凄，這里很明顯是從小往大了推抡驼，也就是說已知小的來寫大的。所以上面的公式更合適的寫法如下：
dp[i] = dp[j] + i/j
然后是初始值肿仑。按照我們的定義致盟，dp[0]可以不用管，dp[1] = 0尤慰，從2開始計算馏锡。默認值和n相等就好，相當于copy1個A然后paste n-1次的操作伟端。
代碼：
# Time: O(n)
# Space: O(n)
class Solution:
def dp(self, n):
dp = [_ for _ in xrange(n + 1)]
dp[1] = 0
for i in xrange(1, n + 1):
for j in reversed(xrange(1, i / 2 + 1)):
if i % j == 0:
dp[i] = dp[j] + i / j
break
return dp[-1]
可以看到杯道，對于j我是從i / 2往回掃的，因為追求copy基數(shù)盡可能大责蝠，而假如j大于i / 2的話怎么樣也不能整除了党巾，所以這里有一點小小的優(yōu)化。
不過霜医，DP解法并不是最優(yōu)的齿拂。
還是回到問題的本質：在最后一個階段，有n/d個A肴敛，然后paste （d-1）次來得到n署海，算上copy總共花費d步。也就是說n必須要被d整除值朋。然后叹侄，那n/d個A又是怎么來的呢？等于又轉到子問題昨登。其實這里還是DP的那個思路趾代。
不過與DP從小往大推不一樣，這里從最后的n往前推丰辣。另外結合了貪婪算法撒强，即希望paste次數(shù)盡可能少禽捆。比如n=1024，我們期望最優(yōu)結果最后是512個A paste 1次而不是1個A paste 1023次飘哨。
參考代碼（原地址）：
public int minSteps(int n) {
int s = 0;
for (int d = 2; d <= n; d++) {
while (n % d == 0) {
s += d;
n /= d;
}
}
return s;
}
d代表divisor胚想，s代表step。因為整除關系是不分先后順序的芽隆，所以d從2開始先把n所有的2因數(shù)掃出來浊服，然后遞增循環(huán)∨哂酰可以想象成從最后逆推的過程牙躺，只不過采用貪婪算法，每次取最小因數(shù)腕扶，此時被paste的A的數(shù)量最多孽拷。
以1024舉例，上一步期望是512半抱，也就是由512 copy paste脓恕，2步；然后再往前推窿侈，期望256炼幔，因為還是能被2整除，依次類推棉磨，很容易知道1024可以由20步產生（到2個A需要2步江掩，之后A的數(shù)目每x2，步數(shù)+2乘瓤，因為1024=2**10环形，所以還需要9*2=18步，總共20步）衙傀。
假如是5的話抬吟，本身是個質數(shù)，只能期望1统抬，所以需要5步火本。
至于復雜度，標題說是O(logn)聪建，我怎么看都是O(n)呢钙畔？
不過，這個算法仍然不是最優(yōu)的金麸。
某種意義上來說擎析，看明白這個題的本質之后，這道題就成了數(shù)學題——求n的所有質因數(shù)之和挥下。
為什么揍魂？代碼就是那個意思啊桨醋。假如n被抽取了所有的2因數(shù)，那還會有4,6這些因數(shù)在嗎现斋？
很容易反證：假如到中間某個因數(shù)不是質因數(shù)喜最，那么它肯定能被分解，分解的因數(shù)肯定比自己小庄蹋，那么為什么這些因數(shù)早些時候沒有被弄出去呢瞬内？
基于這個理論，上面的算法可以優(yōu)化：既然是質因數(shù)限书，那么大小肯定不能超過其開方遂鹊，也就是說
d * d <= n
亦即：
public int minSteps(int n) {
int s = 0;
for (int d = 2; d * d <= n; d++) {
while (n % d == 0) {
s += d;
n /= d;
}
}
return s + (n == 1 ? 0 : n);
}
注意因為d到不了n了，所以d=n的情況要單獨拿出來計算蔗包。
假如n是1，不用擔心慧邮，結果是0调限；
假如n是合數(shù)，也不用擔心误澳，這時候n所有因數(shù)被掏空耻矮，只能是1，最后加0忆谓；
假如n是質數(shù)裆装，這時候之前并沒有d能夠動n，所以n還是它自己倡缠，加上n哨免。
所以最后返回的是s + (n == 1 ? 0 : n)。
順帶貼一個很Hack的方法昙沦，專門針對n的范圍而造的求質因數(shù)和的函數(shù)琢唾，原帖也在上面那個鏈接里面：
public int minSteps(int n) {
// list of primes that are not greater than SQRT(n) - in this case, n = 1,000, SQRT(n) = 31.6
int[] primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31};
int ans = 0;
for (int p : primes) {
while (n % p == 0) {
ans += p;
n /= p;
}
}
return ans + (n == 1 ? 0 : n);
}
基本上就是上面代碼的針對版，既然要求質因數(shù)之和盾饮，那么就只遍歷可能的質因數(shù)采桃，很合理。當然還可以計算哪些質數(shù)滿足d*d<=n丘损，不過這也需要額外的計算力普办。
總結
很有意思的一道題。我覺得這樣的題才算好題：可以從多個角度來解決徘钥，而不是只有一種解法衔蹲。
