[LeetCode] 650. 2 Keys Keyboard

[grandyang]

 

Initially on a notepad only one character 'A' is present. You can perform two operations on this notepad for each step:

1. Copy All: You can copy all the characters present on the notepad (partial copy is not allowed).
2. 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:

1. The n will be in the range [1, 1000].

 

这道题只给了我们两个按键，如果只能选择两个按键，那么博主一定会要复制和粘贴，此二键在手，天下我有！！！果然，这道题就是给了复制和粘贴这两个按键，然后给了一个A，目标时利用这两个键来打印出n个A，注意复制的时候时全部复制，不能选择部分来复制，然后复制和粘贴都算操作步骤，问打印出n个A需要多少步操作。对于这种有明显的递推特征的题，要有隐约的感觉，一定要尝试递归和 DP。递归解法一般接近于暴力搜索，但是有时候是可以优化的，从而能够通过 OJ。而一旦递归不行的话，那么一般来说 DP 这个大杀器都能解的。还有一点，对于这种题，找规律最重要，DP 要找出状态转移方程，而如果无法发现内在的联系，那么状态转移方程就比较难写出来了。所以，从简单的例子开始分析，试图找规律：

当n = 1时，已经有一个A了，不需要其他操作，返回0

当n = 2时，需要复制一次，粘贴一次，返回2

当n = 3时，需要复制一次，粘贴两次，返回3

当n = 4时，这就有两种做法，一种是需要复制一次，粘贴三次，共4步，另一种是先复制一次，粘贴一次，得到 AA，然后再复制一次，粘贴一次，得到 AAAA，两种方法都是返回4

当n = 5时，需要复制一次，粘贴四次，返回5

当n = 6时，需要复制一次，粘贴两次，得到 AAA，再复制一次，粘贴一次，得到 AAAAAA，共5步，返回5

通过分析上面这6个简单的例子，已经可以总结出一些规律了，首先对于任意一个n(除了1以外)，最差的情况就是用n步，不会再多于n步，但是有可能是会小于n步的，比如 n=6 时，就只用了5步，仔细分析一下，发现时先拼成了 AAA，再复制粘贴成了 AAAAAA。那么什么情况下可以利用这种方法来减少步骤呢，分析发现，小模块的长度必须要能整除n，这样才能拆分。对于 n=6，我们其实还可先拼出 AA，然后再复制一次，粘贴两次，得到的还是5。分析到这里，解题的思路应该比较清晰了，找出n的所有因子，然后这个因子可以当作模块的个数，再算出模块的长度 n/i，调用递归，加上模块的个数i来更新结果 res 即可，参见代码如下：

 

解法一：

class Solution {
public:
    int minSteps(int n) {
        if (n == 1) return 0;
        int res = n;
        for (int i = n - 1; i > 1; --i) {
            if (n % i == 0) {
                res = min(res, minSteps(n / i) + i);
            }
        }
        return res;
    }
};

 

下面这种方法是用 DP 来做的，我们可以看出来，其实就是上面递归解法的迭代形式，思路没有任何区别，参见代码如下：

 

解法二：

class Solution {
public:
    int minSteps(int n) {
        vector<int> dp(n + 1, 0);
        for (int i = 2; i <= n; ++i) {
            dp[i] = i;
            for (int j = i - 1; j > 1; --j) {
                if (i % j == 0) {
                    dp[i] = min(dp[i], dp[j] + i / j);
                }
            }
        }
        return dp[n];
    }
};

 

上面的解法其实可以做一丢丢的优化，在遍历j的时候，只要发现了第一个能整除i的j，直接可以用 dp[j] + i/j 来更新 dp[i]，然后直接 break 掉j的循环，之后的j就不用再考虑了，可能是因为因数越大，其需要的按键数就越少吧，参见代码如下：

 

解法三：

class Solution {
public:
    int minSteps(int n) {
        vector<int> dp(n + 1);
        for (int i = 2; i <= n; ++i) {
            dp[i] = i;
            for (int j = i - 1; j > 1; --j) {
                if (i % j == 0) {
                    dp[i] = dp[j] + i / j;
                    break;
                }
            }
        }
        return dp[n];
    }
};

 

下面我们来看一种省空间的方法，不需要记录每一个中间值，而是通过改变n的值来实时累加结果res，参见代码如下：

 

解法四：

class Solution {
public:
    int minSteps(int n) {
        int res = 0;
        for (int i = 2; i <= n; ++i) {
            while (n % i == 0) {
                res += i;
                n /= i;
            }
        }
        return res;
    }
};

 

Github 同步地址：

#650

 

类似题目：

4 Keys Keyboard

Broken Calculator

 

参考资料：

https://leetcode.com/problems/2-keys-keyboard/

https://leetcode.com/problems/2-keys-keyboard/discuss/105899/Java-DP-Solution

https://leetcode.com/problems/2-keys-keyboard/discuss/105928/JavaC%2B%2B-Clean-Code-with-Explanation-4-lines-No-DP

https://leetcode.com/problems/2-keys-keyboard/discuss/105897/Loop-best-case-log(n)-no-DP-no-extra-space-no-recursion-with-explanation

 

LeetCode All in One 题目讲解汇总(持续更新中...)