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 <= N <= 50
- Answers will be in the range of 32-bit signed integer.
看起來和2 keys keyboard有點(diǎn)像，但是并不一樣。這里全選（以下簡稱a），復(fù)制（以下簡稱c），粘貼（以下簡稱v）比之前多了一步，而且問題是給步數(shù)n求能得到最大A的數(shù)量。（平A=直接按A）
注意這個(gè)一開始沒有A，一個(gè)也沒有。
可以先自己手算前幾個(gè)（r代表結(jié)果result）：
n=1,r=1
n=2,r=2
n=3,r=3
這幾個(gè)非常明顯。這時(shí)候應(yīng)該稍微有點(diǎn)意識(shí)了，acv三步走實(shí)現(xiàn)加倍，如果本身比3小，那是不如平A的。
n=4，r=4
這時(shí)候n比3大，但還是不能用acv，因?yàn)閍cv必須要求至少3步，少了什么也沒有，如果這里硬要用的話只能對(duì)1個(gè)A使用，太不劃算。
這時(shí)候應(yīng)該能想到，要想讓acv三步至少不虧，那么之前至少要留有3個(gè)A，也就是說n=6的時(shí)候不虧。即：
n=6,r=6
前面的5自然還是一個(gè)個(gè)A拼出來：n=5,r=5
n=7的時(shí)候，又是一個(gè)需要思考的地方。按前面說的，6個(gè)A可以通過平A得到，也可以3個(gè)A再acv，acv的方法肯定更優(yōu)，因?yàn)榻o后面留下了繼續(xù)v的可能。
所以如果從n=6加v，結(jié)果是9.
當(dāng)然還需要考慮使用acv的不同情況?？赡苄砸呀?jīng)有不少了，比如只使用一輪acv+（+指1個(gè)或多個(gè)），或者極限的話可以在A之后使用連續(xù)兩輪acv。這些結(jié)果都不如9大，但是可以提供一些思路。
到這里其實(shí)沒太多必要繼續(xù)推下去了。從最優(yōu)角度來看，除了前面平A，后面應(yīng)該都要用acv+及其組合。因?yàn)檫@里只給了步數(shù)，并不存在要套數(shù)字或者溢出的問題，所以盡量爭取A的數(shù)量最多。
也就是說最優(yōu)解應(yīng)該是這種形狀：
初始若干平A + （acv+）+（acv+）...
關(guān)于acv的效率，3步相當(dāng)于x2,4步（acvv）相當(dāng)于x3,5步相當(dāng)于x4，或者設(shè)acv+步數(shù)為k，那么效果是x（k-1）。
說了這么多，有什么用呢？
其實(shí)這些就是問題的本質(zhì)。相當(dāng)于動(dòng)態(tài)規(guī)劃。因?yàn)榭偛綌?shù)一定，目的就是讓這些數(shù)乘起來盡可能大。
當(dāng)然這里面還摻雜了初始平A這種東西。至少得3次平A之后再使用acv。
其實(shí)有鑒于上一道題，我本來一開始想嘗試數(shù)學(xué)解法，結(jié)果還是不行?？磥砻嬖嚨臅r(shí)候還是直接奔DP比較靠譜。當(dāng)然有大神掏出了O（1）的數(shù)學(xué)解法，我表示牛到不行，只能佩服。后面有講，總之?dāng)?shù)學(xué)解法難度是ACM級(jí)別的（臆測）。
DP就不同了，只要知道關(guān)系式就行。
這里的話，很明顯有子問題。拿上面的形狀來說：
初始若干平A + （acv+）+（acv+）...
我們可以單獨(dú)把最后一個(gè)acv+拿出來，拿它的長度做文章。
設(shè)dp[i]是i步能獲得的最大A數(shù)量，因?yàn)樗偸且詀cv+結(jié)尾（假設(shè)i>=6），其長度在3~（i-3）之間。我們可以遍歷這個(gè)長度，結(jié)合之前剩下的dp，來取一個(gè)最大值。也就是說
for j in xrange(3, i - 2):
dp[i] = max(dp[i], dp[i-j]*(j-1))
更詳細(xì)的解釋：i指目前我們考慮的下標(biāo)，j是最后acv+的長度，按照之前說的acv+長度為j，那么效果就是乘以（j-1），剩下的部分長度為i-j，之前已經(jīng)算過了直接拿出來就好。要做的就是遍歷長度j可能的值計(jì)算dp[i]，然后取一個(gè)最大值。
完整代碼：
# Time: O(n^2)
# Space: O(n)
class Solution(object):
def maxA(self, n):
dp = [_ for _ in xrange(n + 1)]
for i in xrange(7, n + 1):
for j in xrange(3, i - 2):
dp[i] = max(dp[i], dp[i - j] * (j - 1))
return dp[-1]
時(shí)間復(fù)雜度不能說很好，但是怎么說也算是解答了問題。
然后是數(shù)學(xué)解法，參加一畝三分地的帖子。
還是回到上面的動(dòng)態(tài)規(guī)劃那里，轉(zhuǎn)化為如下動(dòng)態(tài)規(guī)劃問題：
已知N，求x0 * x1 * ... * xk最大值，有：
x0 + x1 + ... + xk = N - k
k >= 0
x0 >= 1
x1, ..., xk >= 2
這里的x0就是初始平A，x1~xk就是acv+，其長度>=3，乘起來效果就是>=2。
那么給定N，如何求k呢？
4 * (k + 1) - delta = N - k, where 0 <= delta <= 4
k = (N + delta - 4) / 5 = N / 5
這里需要解釋一下。結(jié)論就是優(yōu)先使用4作為乘數(shù)，其次用3.
為什么？這里有一個(gè)“貢獻(xiàn)因子”的理論，也就是說長度為x貢獻(xiàn)x-1的乘數(shù)，貢獻(xiàn)因子是(x-1)^(1/x)，
x=2因子為1，x=3因子為1.26，x=4因子為1.316，x=5因子為1.320，x=6因子為1.308.
也就是說acv+的長度盡可能取5，其次是4，反映到乘數(shù)里面就是優(yōu)先用4，其次用3了。
具體代碼如下：
# Time: O(1)
# Space: O(1)
def maxA(self, N):
"""
:type N: int
:rtype: int
"""
if N < 7: return N
if N == 10: return 20 # the following rule doesn't hold when N = 10
n = N // 5 + 1 # n3 + n4 increases one every 5 keys
# (1) n = n3 + n4
# (2) N + 1 = 4 * n3 + 5 * n4
# 5 x (1) - (2) => 5*n - N - 1 = n3
n3 = 5 * n - N - 1
n4 = n - n3
return 3 ** n3 * 4 ** n4
n就是上面的k+1，理想情況下由x3的因子n3和x4的因子n4組成。
然后呢？就看不懂了……
又想了一下，這個(gè)意思應(yīng)該是把平A也假設(shè)成為3或者4，否則結(jié)果里面沒有說不過去。
那為什么只是N+1= 4 * n3 + 5 * n4呢？
因?yàn)樽髡甙哑紸也歸納到n里面去了！換言之，作者把x0轉(zhuǎn)化當(dāng)成了一個(gè)acv+！
想想無論是平A=3還是4，就乘積效果而言相比acv+，都是省1步的！
所以這么寫更好理解：N = 4 * n3 + 5 * n4 - 1
之后就一切自然而然了，然而還有一個(gè)特例就是10不遵守這個(gè)條件……
作者原話是：
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.
按照之前的算法n=3，然而即使是最小的組合3+4+4也超了，所以不成立。反映到計(jì)算就是n4=-1.
總而言之，這個(gè)算法充滿神奇，多個(gè)大膽的假設(shè)，然后最后還是對(duì)的。臨場還是別抱數(shù)學(xué)解法的想法吧……
彩蛋：一個(gè)基于數(shù)學(xué)解法的DP……
# Time: O(n)
# Space: O(1)
class Solution2(object):
def maxA(self, N):
"""
:type N: int
:rtype: int
"""
if N < 7: return N
dp = range(N + 1)
for i in xrange(7, N + 1):
dp[i % 6] = max(dp[(i - 4) % 6] * 3, dp[(i - 5) % 6] * 4)
return dp[N % 6]
我一開始不太明白i%6是否有特別含義，對(duì)我而言這是滾動(dòng)DP，按道理3個(gè)格子夠用了？
想一想，i=7的時(shí)候需要dp[2]和dp[3]的值，為了不沖突，所以把值放到dp[1]，很合理的解釋。
試了一下，把所有%6改成%7，結(jié)果不變，說明我的猜測是正確的。事實(shí)上可以單獨(dú)拿3個(gè)格子出來裝，不過牽涉到初始值的問題麻煩一點(diǎn)。
另外dp = range(N + 1)改成dp = range(7)也不會(huì)有任何問題。
總結(jié)
數(shù)學(xué)解法超乎想象。
