1. 概述

描述

ENG 假设有一个特殊的键盘，键盘上有如下键:

  • 键1: (A): 在屏幕上打印一个’A’。
  • 键2: (Ctrl-A): 选择整个屏幕。
  • 键3: (Ctrl-C): 复制选择到缓冲区。
  • 键4: (Ctrl-V): 在屏幕上已有的内容后面追加打印缓冲区的内容。

现在，只能按键盘上N次(使用以上四个键)，找出可以在屏幕上打印的“A”的最大数量

  1. 1 <= N <= 50
  2. 答案将在32位有符号整数的范围内。

    样例

样例 1:

  1. 输入: 3
  2. 输出: 3
  3. 解释: A, A, A

样例 2:

  1. 输入: 7
  2. 输出: 9
  3. 解释: A, A, A, Ctrl A, Ctrl C, Ctrl V, Ctrl V

相关题目

  1. 只有2个按键的键盘

2. 解题

  1. <?php
  2. class Solution
  3. {
  4.     public function maxA(int $n)
  5.     {
  6.         $res = $n;
  7.         for ($i = 1; $i < $n - 2; ++$i) {
  8.             $res = max($res, $this->maxA($i) * ($n - 1 - $i));
  9.         }
  10.         return $res;
  11.     }
  13.     // N次操作最少能打出N个A，且如果最后的一组操作是acv(vvv...)打出的A的个数比干敲多之后，先用acv再干敲肯定是不划算的
  14.     // (因为如果把干敲放在acv前面，打出来的肯定更多)。那么我们要考虑的就是最后一个acvvvv....，v多少次是最优解。
  15.     // 如果只v一次，res[N]=res[N-3]*2(留出3次操作acv，v了一次，加上已有的res[N-3],是2*res[N-3])；
  16.     // 如果v两次，res[N]=res[N-4]*3(acvv,复制两次加已有的一组，一共四组)....以此类推找到最优解。
  17.     public function maxA2(int $n) {
  18.         $res = [];
  19.         for ($i = 1; $i <= $n; $i++)
  20.         {
  21.             $res[$i] = $i;
  22.             for ($j = $i - 3; $j >= 1; $j--)
  23.                 $res[$i] = max($res[$i], $res[$j] * ($i - $j - 1));
  24.         }
  25.         return $res[$n];
  26.     }
  27. }
  29. $cls = new Solution();
  30. // $r = $cls->maxA(10);
  31. $r = $cls->maxA2(10);
  32. echo $r;