Leetcode:No.650 2 Keys Keyboard

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所需要的最少步数。
那么很明显就有一个关系：在得到dp[i]的前提下，我们可以copy然后paste任意次数，也就是说
dp[k*i]=dp[i] + k ，其中k是大于1的正整数，copy1次paste k-1次。
连续copy没有意义，所以最优的单元操作一定是一个copy加上1到若干个paste。这个公式就涵盖了所有最优单元操作。
当然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基数尽可能大，而假如j大于i / 2的话怎么样也不能整除了，所以这里有一点小小的优化。

不过，DP解法并不是最优的。
还是回到问题的本质：在最后一个阶段，有n/d个A，然后paste （d-1）次来得到n，算上copy总共花费d步。也就是说n必须要被d整除。然后，那n/d个A又是怎么来的呢？等于又转到子问题。其实这里还是DP的那个思路。
不过与DP从小往大推不一样，这里从最后的n往前推。另外结合了贪婪算法，即希望paste次数尽可能少。比如n=1024，我们期望最优结果最后是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因数扫出来，然后递增循环。可以想象成从最后逆推的过程，只不过采用贪婪算法，每次取最小因数，此时被paste的A的数量最多。
以1024举例，上一步期望是512，也就是由512 copy paste，2步；然后再往前推，期望256，因为还是能被2整除，依次类推，很容易知道1024可以由20步产生（到2个A需要2步，之后A的数目每x2，步数+2，因为1024=2**10，所以还需要9*2=18步，总共20步）。
假如是5的话，本身是个质数，只能期望1，所以需要5步。
至于复杂度，标题说是O(logn)，我怎么看都是O(n)呢？

不过，这个算法仍然不是最优的。
某种意义上来说，看明白这个题的本质之后，这道题就成了数学题——求n的所有质因数之和。
为什么？代码就是那个意思啊。假如n被抽取了所有的2因数，那还会有4,6这些因数在吗？
很容易反证：假如到中间某个因数不是质因数，那么它肯定能被分解，分解的因数肯定比自己小，那么为什么这些因数早些时候没有被弄出去呢？
基于这个理论，上面的算法可以优化：既然是质因数，那么大小肯定不能超过其开方，也就是说
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是合数，也不用担心，这时候n所有因数被掏空，只能是1，最后加0；
假如n是质数，这时候之前并没有d能够动n，所以n还是它自己，加上n。
所以最后返回的是s + (n == 1 ? 0 : n)。

顺带贴一个很Hack的方法，专门针对n的范围而造的求质因数和的函数，原帖也在上面那个链接里面：

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);
}

基本上就是上面代码的针对版，既然要求质因数之和，那么就只遍历可能的质因数，很合理。当然还可以计算哪些质数满足d*d<=n，不过这也需要额外的计算力。

总结

很有意思的一道题。我觉得这样的题才算好题：可以从多个角度来解决，而不是只有一种解法。