LeetCode#650 2 Keys Keyboard题解（C++版）

题干

原题网址： https://leetcode.com/problems/2-keys-keyboard/description/

题干解析

输入一个[1, 1000]之间的整数n，代表目标需要生成的A的个数。给你的文本上初始化有一个A，你对文本只能有以下两种操作，最后要让文本上有n个A，找出最小的操作次数。 操作1：Copy all，即复制当前文本的所有字符。 操作2：粘贴。

知识点

动态规划

难度

中等

解题思路

这道题可以用动态规划来解，也可以不用动态规划来解。 1.动态规划解版 因为只有两种操作，我们每一步做决策时只需要考虑如下两种情况：是要先复制一下再粘贴，还是不复制就粘贴。对于每一步，我们算出进行这种操作后，需要多少个操作能达到目标状态所需要的总次数（或者无法达到），然后取较小次数那一次便可。 2.非动态规划版 同上面所说，我们要么先复制再粘贴，要么不复制直接粘贴。而很显然，复制板上A的长度是只增不减的，且每次复制之后，复制板上A的长度是之前复制板上A的长度的倍数，所以如果复制后的复制板上的长度无法被剩下需要生成的A的个数所整除的话，我们就不可以复制，否则后面的A的长度要超过所需的长度，即无解。而如果可以被整除，我们为了得到较少的操作次数，就要先复制（想象一下，复制虽然会多了一次操作，但是复制后复制板上的A的长度至少是原先复制板上A的长度的两倍（如果上一次没有复制直接粘贴的话，长度不止两倍）。如果不复制，至少也要两次粘贴才能达到刚刚复制一次再粘贴一次的效果。所以，能复制的时候就尽管复制，顶多也就和不复制直接粘贴扯平）。因此，代码写起来非常简洁。

代码

//动态规划解法 int MAX = 1001; class Solution { public: int dp(int n, int have, int c) { //have代表已经有了几个A，c代表当前复制板上有几个A if (n == have) { // 如果已经到达目标，返回0 return 0; } else if (n < have) { // 如果超出了目标，则代表无解，返回MAX return MAX; } else if ((n - have) % c != 0) { // 如果已经不能被整除，无解（因为have一定是c的倍数，此时再复制也无意义) return MAX; } int temp1 = 2 + dp(n, have * 2, have); // 复制一次加粘贴一次 int temp2 = 1 + dp(n, have + c, c); // 不复制，只粘贴 if (temp1 > temp2) { //哪种操作次数少，返回哪一种 return temp2; } else { return temp1; } } int minSteps(int n) { if (n <= 1) { return 0; } return dp(n, 1, 1) + 1; } }; class Solution { public: int minSteps(int n) { if (n <= 1) { // 如果需要的长度小于等于1，那就不需要操作了，直接返回0 return 0; } int ans = 0; // 初始化操作的次数 int left = n - 1; // 剩下还未生成的A的个数 int paste = 1; // 复制板上A的个数，一开始肯定要先复制一下，初始化为1 left -= paste; // 第一次复制之后肯定要粘贴，所以剩下的未生成的A减1 ans += 2; // 一次复制一次粘贴，已经操作了两次 while (left > 0){ if (left % (n - left) == 0) { // 如果剩下的需要生成的A的个数能够整除当前A的个数，那么复制全部，然后粘贴一次 paste = n - left; left -= paste; ans += 2; } else { // 否则，因为复制版长度只增不减，若当下不能整除，复制后的复制版内容长度是当前的长度的倍数，同样不能整除。所以直接粘贴 left -= paste; ans += 1; } } return ans; } };