[leetcode] 650. 2 Keys Keyboard (Medium)

解法一：

暴力DFS搜索，对每一步进行复制还是粘贴的状态进行遍历。

注意剪枝的地方：

1、当前A数量大于目标数量，停止搜索

2、当前剪贴板数字大于等于A数量时，只搜索下一步为粘贴的状态。

Runtime: 8 ms, faster than 46.69% of C++ online submissions for 2 Keys Keyboard.

class Solution
{
public:int targetNum = 0;int resNum = INT_MAX;int minSteps(int n){targetNum = n;if (n == 1)return 0;dfs(1, 1, 1);return resNum;}void dfs(int copy, int curNum, int times){if (curNum == targetNum){resNum = min(times, resNum);return;}else if (curNum >= targetNum)return;else if (copy >= curNum)dfs(copy, curNum + copy, times + 1);else{dfs(curNum, curNum, times + 1);dfs(copy, curNum + copy, times + 1);}}
};

解法二：

当n >= 2的时候，最优策略就是尽可能地生成n的最大因数（n / d）个A，然后进行 Copy 一次 Paste d - 1次操作，

为使n / d尽可能的大，只能使d尽可能的小，于是d从2开始循环。当找到一个d之后，我们接下来只需要解决生成n /d个A的问题，所以在循环中让n变为n / d即可。时间复杂度降低到了O(logn)。
Runtime: 0 ms, faster than 100.00% of C++ online submissions for 2 Keys Keyboard.

class Solution
{
public:int minSteps(int n){int res = 0;int d = 2;while (n > 1){while (n % d == 0){res += d;n /= d;}d++;}return res;}
};