1. 概述

初始时在记事本上只有一个字符 ‘A’。可以在此记事本上每一步可以进行两种操作：

  1. Copy All: 复制记事本上所有的字符（不允许部分复制）
  2. Paste: 粘贴上一次复制的字符。

给出一个数字 n，需要在记事本上得到恰好 n 个 ‘A’， 问最少需要几步。

注：n 在范围 [1, 1000] 内

例1:

  1. 输入: 3
  2. 输出: 3
  3. 解释:
  4. Intitally, we have one character 'A'.
  5. In step 1, we use Copy All operation.
  6. In step 2, we use Paste operation to get 'AA'.
  7. In step 3, we use Paste operation to get 'AAA'.

例2:

  1. 输入: 1
  2. 输出: 0

2. 解题

2.1 解题思路

  1. 每个正常输入的数都可以由一个 A 变为 n 个 A
  2. 要获取 n 个 A，并且是使用最小的步数的时候，可以得出在 m 次操作之后的下一步是粘贴（1步操作），或者是复制后粘贴（2步操作），如下：
    1. 如果是复制后粘贴，那么这个数一定是n的一半大小；
    2. 如果是粘贴，那么就有多种可能性了，可能粘贴的数以及连续粘贴的次数时未知的。
  3. 那么这里需要两个空间来记录状态：
    1. f(n) 记录最少步数能得到 n 个 A；
    2. o(n) 记录得出 f(n) 时当前复制的 A 的数量。
  4. 所以按照第二步的推理，可以把 n 分为奇偶数处理：
    1. 如果是偶数，则取 f(n) = f(n/2) + 2 。
    2. 如果是奇数，遍历回溯 n-x: (n-1 n-2 n-3 ... 2 1) 直到找到能实现 n = (n-x) + (o(n-x) * k) 的 x 和 k，然后 f(n) = f(n-x) + k 。

      2.2 解题代码

      ```php <?php

class Solution { /**

  1.  * @param int $n
  2.  * @return int : the minimum number of steps to get n 'A'
  3.  */
  4. public function minSteps(int $n): int
  5. {
  6.     if ($n < 0) {
  7.         return -1;
  8.     }
  10.     /** @var array $minStep 需要的A长度为$i时，最小的操作步数 */
  11.     $minStep[1] = 0;
  12.     /** @var array $copyNums 当$minStep[$i]存在时， $copyNums[$i]为当前复制的A数量 */
  13.     $copyNums[1] = 0;
  15.     for ($i = 2; $i <= $n; $i++) {
  17.         // 偶数一定可以取到折半的数进行：复制、粘贴
  18.         if ($i % 2 == 0) {
  19.             $minStep[$i] = $minStep[$i / 2] + 2;
  20.             $copyNums[$i] = $i / 2;
  21.         } else {
  22.             // 回溯记录的之前复制过的值，进行多次粘贴是否能得到需要的值
  23.             for ($j = $i - 1; $j > 0; $j--) {
  24.                 $k = 1;
  25.                 while (1) {
  26.                     $value = $j + ($copyNums[$j] * $k);
  27.                     if ($value < $i) {
  28.                         $k++;
  29.                         continue;
  30.                     } elseif ($value > $i) {
  31.                         break;
  32.                     } else {
  33.                         $minStep[$i] = $minStep[$j] + $k;
  34.                         $copyNums[$i] = $copyNums[$j];
  35.                         break 2;
  36.                     }
  37.                 }
  38.             }
  39.         }
  40.     }
  42.     return $minStep[$n];
  43. }

}

$n = 1000; $cls = new Solution(); $cls->minSteps($n); ```