LeetCode 651. 4 Keys Keyboard 数学解法看不懂(O(1)空间和O(1)时间)求大神点化

题目链接: 651. 4 Keys Keyboard

因为是付费题, 所以题目描述贴在这里:
Imagine you have a special keyboard with the following keys:

Key 1: (A): Prints one 'A' on screen.

Key 2: (Ctrl-A): Select the whole screen.

Key 3: (Ctrl-C): Copy selection to buffer.

Key 4: (Ctrl-V): Print buffer on screen appending it after what has already been printed.

Now, you can only press the keyboard for N times (with the above four keys), find out the maximum numbers of 'A' you can print on screen.

Example 1:
```
Input: N = 3
Output: 3
Explanation:
We can at most get 3 A's on screen by pressing following key sequence:
A, A, A
```
Example 2:
```
Input: N = 7
Output: 9
Explanation:
We can at most get 9 A's on screen by pressing following key sequence:
A, A, A, Ctrl A, Ctrl C, Ctrl V, Ctrl V
```
Note:
1. 1 <= N <= 50
2. Answers will be in the range of 32-bit signed integer.

Difficulty:Medium
Total Accepted:2.5K
Total Submissions:5.3K
Contributor: fallcreek
Companies
Microsoft Google
Related Topics
Math Greedy Dynamic Programming
Similar Questions
2 Keys Keyboard


这个题目标准的最优解是DP, 最简单的做法是N^2复杂度, 然后可以优化到N. 但是这种DP做法不是我问的. discussion有人发了一个帖子, 公布了一个O(1)时间和空间的math解法: https://discuss.leetcode.com/top ... rtest-and-fastest/3

1. int maxA(int N) {
   
2.     if (N <= 6) return N;
   
3.     if (N == 10) return 20;
   
4.     int n = N / 5 + 1, n3 = n * 5 - 1 - N;
   
5.     return pow(3, n3) * pow(4, n - n3);
   
6. }

复制代码

这是原作者的解释:
> Pure math. This problem is to partition number N into 3's and 4's and get their product. n = N / 5 + 1is to compute the number of factors(the total number of 3's and 4's). With n, it's easy to know how many out of them are 3's by computing n3 = n * 5 - 1 - N. We minus 1 here because adding a single factor requires one step more than the factor itself, e.g. x4 takes 5 steps (select all, copy, paste, paste, paste). 10 is special here because it's the only > 6 number where there is no enough factors to share cuts from decrement of the number of 3's which means a 5 has to be introduced.


课时还是不太看得懂. 感觉是他的思路里面有什么重要的insight我没有捕捉到, 请教一下有没有大神能指点一二.

这里大概写一下几个Insights.. 不过相关证明比较麻烦，就简单带过了

定义1：按键序列
首先为了方便我们用一个长度为N的字符串来表示一个按键序列，其中大写A表示按下字母'A'，小写a表示按下Ctrl + A，小写c表示按下Ctrl + C，小写v表示按下Ctrl + V。

例如AAacvvacvv是对于N=10的一个按键序列，会生成18个'A'。

定义2：规范序列
如果一个按键序列满足正则表达式A+(acv+)*，那么我们称其为一个规范（canonical）按键序列，简称规范序列。
换言之，一个规范序列：
(1) 所有A都在最前面
(2) 所有a都紧接在A或者v后面
(3) 所有c都紧接在a后面
(4) 所有v都紧接在c或者v后面

关键定理3：对于任意N，设长度为N的按键序列能够生成的最大'A'的数量为opt(N)，那么存在长度为N的规范序列S，使得S生成的'A'的数量等于opt(N)。

这个定理的意思是说，要找最优解，我们只要考虑规范序列就可以了——这样就大大简化了我们的讨论范围。

定理3要证明还是很繁琐的，要分类讨论然后用数学归纳法。思路大致就是给定任意一个生成最大数量'A'的非规范序列，我们可以各种微调将其变换为一个规范序列，并且生成的'A'的数量不少于原来的非规范序列。

现在，在定理3的基础上，问题缩小到了如何找到最优的规范序列。

一个规范序列最终会生成多少个'A'呢？我们可以观察一下几个针对N=10的例子：
(1) AA acvv acvv
  => 2 * 3 * 3 = 18
(2) AAAA acv acv
  => 4 * 2 * 2 = 16
(3) AAAAA acvvv
  => 5 * 4 = 20

注意到上面三个例子中，我们用空格隔开了所有(A+)和(acv+)，而生成的'A'的数量即为(A+)的字符数量以及各个(acv+)的字符数量减1的累乘积。

也就是说，给定一个N，我们需要确定'A'的数量x0，以及(acv+)的数量k，以及这k个(acv+)各自的长度x1, ..., xk，使得：
  x0 + x1 + ... + xk = N
并且最大化：
  x0 * (x1 - 1) * ... * (xk - 1)

将以上式子稍作变形后，我们得到：

关键定理4：给定任意N，最大生成'A'的数量等价于以下优化问题的解。
Maximize:
  x0 * x1 * ... * xk

Subject to:
  x0 + x1 + ... + xk = N - k
  k >= 0
  x0 >= 1
  x1, ..., xk >= 2

这是一个变量数不定的整数规划问题，我不知道用什么数学工具去形式化地分析它.. 但是应该可以用数学归纳法证明所有x的取值优先为4，其次取3；因为“1单位值对乘积的贡献"为 4^(1/5) > 3^(1/4) > 其它（2^(1/3), 5^(1/6), etc.）。

再回过来看原来的解答：

Pure math. This problem is to partition number N into 3's and 4's and get their product. n = N / 5 + 1is to compute the number of factors(the total number of 3's and 4's). With n, it's easy to know how many out of them are 3's by computing n3 = n * 5 - 1 - N. We minus 1 here because adding a single factor requires one step more than the factor itself, e.g. x4 takes 5 steps (select all, copy, paste, paste, paste). 10 is special here because it's the only > 6 number where there is no enough factors to share cuts from decrement of the number of 3's which means a 5 has to be introduced.

这实际上是在说如何解定理4中的优化问题——原作者并没有解释为什么这么解是对的，但是作者假定正确解就是
x的取值优先取4，如果无法余尽，那么调整一部分到3。不过N=10的情况是例外，此时我们取x0=5, x1 = 4, k = 1（或者x0 = 4, x1 = 5, k = 1）。

比如N = 12，那么我们选x0 = 4, x1 = 3, x2 = 3，这样k = 2满足约束x0 + x1 + x2 = N - k
最优解即为4 * 3 * 3 = 36

那么，给定一个任意N，怎么求k呢？就是原作者用的那个式子（N / 5 + 1实际上是求的我们这边式子中的k+1，也就是说k = N / 5，注意到这里的'/'是整数除法)。

推导过程大致如下，首先列方程：
4 * (k + 1) - delta = N - k, where 0 <= delta <= 4

所以：
k = (N + delta - 4) / 5 = N / 5

PS: 为什么(N + delta - 4) / 5 = N / 5？
-- 注意到5整除N + delta - 4，而0 >= delta - 4 >= -4，所以N/5不会进一，还是等于(N + delta - 4) / 5

楼主自我要求很高啊。我看到pure math就直接pass了。

bearicc 发表于 2017-8-18 02:29
楼主自我要求很高啊。我看到pure math就直接pass了。

怕碰到不讲道理的面试官啊. 之前不是还有个哥们儿被要求给出一个优于N^2的3sum解法来的..虽然那个有点过分, 不过我感觉真正面试如果碰到这种问题被问到一个math解还是有可能的.

另: math解我一般也是不太认真看的, 大概理解一下就拉倒了. 不过这个解实在是一点头绪都没有所以只要厚脸皮来问一下.

vegito2002 发表于 2017-8-18 02:36
怕碰到不讲道理的面试官啊. 之前不是还有个哥们儿被要求给出一个优于N^2的3sum解法来的..虽然那个有点过 ...

那不是比较过分

那是相当过分

3 sum的时间复杂度下限至今还没有人知道：
https://en.m.wikipedia.org/wiki/3SUM

碰上这种面试官就只好听天命了

在重要的面试里遇到 就只好。。。呵呵

这题我上大学时自己想到过（想到过题设，一模一样，不过没想过答案）还在我们学校论坛给大家出了一下，结果有个搞ACM的说这是某ACM竞赛题。。没想到LC也有这题了。

有些公司面试题难度的方差太大了，很不公平

Mark一下，同求解答
话说，楼主的头像也是醉了。。。

magicsets 发表于 2017-8-31 02:30
这里大概写一下几个Insights.. 不过相关证明比较麻烦，就简单带过了

定义1：按键序列

感谢朱神, 我认为你的分析和证明是对的, 不过我还是再继续花点时间去自己咂摸一下这个作者自己本来到底是什么思路;

另外, 你这里: “1单位值对乘积的贡献"为 4^(1/5) > 3^(1/4) > 其它（2^(1/3), 5^(1/6), etc.）。这个是什么思想?

另外, 我记得LeetCode好像之前做过一个题目, 就是给定一个sum, 然后要你拆分成随便多的数字, 使product最大; 当时的discussion里面好像就有讨论, 因为这个题目是一个递归做的, 在递归的每一个level, 都要决定拆出去多少的数字, 当时就有人讨论说, 拆除3或者4好像始终是最好的解法; 好像有一个粗糙的证明, 这会儿想不起来了是哪个题目了;

另外, 之前我请教过的那一道Majority Element的最优解法的不知道你是不是还记得了, 那个解法后来我找到了一个paper, Moore voting最后需要2N次比较, 而这个最优解法需要3N/2 -2 次比较; paper里面还有证明其optimality;
是1982年的一篇很老的paper了: http://www.cs.yale.edu/publications/techreports/tr252.pdf

另外, 你这里: “1单位值对乘积的贡献"为 4^(1/5) > 3^(1/4) > 其它（2^(1/3), 5^(1/6), etc.）。这个是什么思想?

这个之前偷懒了没写清楚..

考虑一个例子：
AAA acvv acvvv

对于这个例子，生成的'A'的数量是 3 * (4 - 1) * (5 - 1) = 36

注意到acvv长度是4，贡献了因子(4 - 1) = 3；acvvv长度是5，贡献了因子(5 - 1) = 4。

那么acvv“单位长度”的贡献就是3^(1/4)约等于1.316，而acvvv“单位长度”的贡献就是4^(1/5)约等于1.320。

也就是说，在可以除尽的情况下，使用acvvv比acvv更划算。

例如考虑
(1) ... acvv acvv acvv acvv acvv
(2) ... acvvv acvvv acvvv acvvv

同样是20次按键，5组acvv提供的乘积因子为 (3^(1/4))^20 = 3 ^ 5 = 243，而4组acvvv提供的乘积因子为(4^(1/5))^20 = 4 ^ 4 = 256。