LeetCode 651 - 4 Keys Keyboard

Related: LeetCode 650 - 2 Keys Keyboard
https://leetcode.com/problems/4-keys-keyboard/description/

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.

http://www.cnblogs.com/grandyang/p/7448390.html

这道题给了我们四个操作，分别是打印A，全选，复制，粘贴。每个操作都算一个步骤，给了我们一个数字N，问我们N个操作最多能输出多个A。我们可以分析题目中的例子可以发现，N步最少都能打印N个A出来，因为我们可以每步都是打印A。那么能超过N的情况肯定就是使用了复制粘贴，这里由于全选和复制要占用两步，所以能增加A的个数的操作其实只有N-2步，那么我们如何确定打印几个A，剩下都是粘贴呢，其实是个trade off，A打印的太多或太少，都不会得到最大结果，所以打印A和粘贴的次数要接近，最简单的方法就是遍历所有的情况然后取最大值，打印A的次数在[1, N-3]之间，粘贴的次数为N-2-i，加上打印出的部分，就是N-1-i了

    int maxA(int N) {
        int res = N;
        for (int i = 1; i < N - 2; ++i) {
            res = max(res, maxA(i) * (N - 1 - i));
        }
        return res;
    }

这道题也可以用DP来做，我们用一个一维数组dp，其中dp[i]表示步骤总数为i时，能打印出的最多A的个数，初始化为N+1个，然后我们来想递推公式怎么求。对于dp[i]来说，求法其实跟上面的方法一样，还是要遍历所有打印A的个数，然后乘以粘贴的次数加1，用来更新dp[i]

    int maxA(int N) {
        vector<int> dp(N + 1, 0);
        for (int i = 0; i <= N; ++i) {
            dp[i] = i;
            for (int j = 1; j < i - 2; ++j) {
                dp[i] = max(dp[i], dp[j] * (i - j - 1));
            }
        }
        return dp[N];
    }

http://reeestart.me/2018/12/09/LeetCode-651-4-Keys-Keyboard/

不算特别难, 对于dp[i]来说, 有三种情况需要考虑:

1. worst case就是敲i个A出来.
2. 第二种情况就是在i - 3的位置开始 ctrl-A, ctrl-C, ctrl-V, 那么结果就是dp[i - 3] \ 2*
3. 还有一种情况就是在[0, i - 3)区间的某个位置, ctrl-A, ctrl-C, ctrl-V之后, 接下来狂摁ctrl-V, 那么结果就应该是: dp[j] \ (i - j - 1)*

public int maxA(int N) {

if (N <= 6) return N;



final int[] dp = new int[N + 1];

for (int i = 0; i <= N; i++) {

dp[i] = i;

}



for (int i = 7; i <= N; i++) {

dp[i] = Math.max(dp[i], dp[i - 3] * 2);

for (int j = 1; j <= i - 3; j++) {

final int tmp = dp[j] * (i - j - 1);

dp[i] = Math.max(dp[i], tmp);

}

}



return dp[N];

}

https://coldq.github.io/hexo/2017/10/02/leetcode_contest43/

动态规划，将dp[i]作为i个操作能得到的最多A的数量。

dp[n]，n>3时，可以是 Ctrl A, Ctrl C, Ctrl V得到的，那么这个Ctrl A从哪开始呢？

如果是从n-3(复制操作需要3步,n-3是能开始复制的最后)开始复制,那只能复制一次,即2dp[n-3],或者更早开始，依次为3dp[n-4],4dp[n-5],直至(n-2)dp[1],(有没有更早的终止条件？)
取之中最大的值，再和直接输入n次A即n比较，较大者即是dp[n]。

var maxA = function(N) {
    let dp = [0,1,2,3];
    for(let i = 4;i<=N;i++){
        let j = i-3,c=2;
        while(j>=1){
            if(dp[i] === void 0)dp[i]=dp[j]*c;
            else dp[i] = Math.max(dp[i],dp[j]*c);//从第几个开始乘
            c++;
            j--;
        }
        dp[i] = Math.max(i,dp[i]);
    }
    return  dp[N];
};

https://www.jianshu.com/p/ee57e9ae02e5

看起来和2 keys keyboard有点像，但是并不一样。这里全选（以下简称a），复制（以下简称c），粘贴（以下简称v）比之前多了一步，而且问题是给步数n求能得到最大A的数量。（平A=直接按A）
注意这个一开始没有A，一个也没有。
可以先自己手算前几个（r代表结果result）：
n=1,r=1
n=2,r=2
n=3,r=3
这几个非常明显。这时候应该稍微有点意识了，acv三步走实现加倍，如果本身比3小，那是不如平A的。
n=4，r=4
这时候n比3大，但还是不能用acv，因为acv必须要求至少3步，少了什么也没有，如果这里硬要用的话只能对1个A使用，太不划算。
这时候应该能想到，要想让acv三步至少不亏，那么之前至少要留有3个A，也就是说n=6的时候不亏。即：
n=6,r=6
前面的5自然还是一个个A拼出来：n=5,r=5
n=7的时候，又是一个需要思考的地方。按前面说的，6个A可以通过平A得到，也可以3个A再acv，acv的方法肯定更优，因为给后面留下了继续v的可能。
所以如果从n=6加v，结果是9.
当然还需要考虑使用acv的不同情况。可能性已经有不少了，比如只使用一轮acv+（+指1个或多个），或者极限的话可以在A之后使用连续两轮acv。这些结果都不如9大，但是可以提供一些思路。
到这里其实没太多必要继续推下去了。从最优角度来看，除了前面平A，后面应该都要用acv+及其组合。因为这里只给了步数，并不存在要套数字或者溢出的问题，所以尽量争取A的数量最多。
也就是说最优解应该是这种形状：
初始若干平A + （acv+）+（acv+）...
关于acv的效率，3步相当于x2,4步（acvv）相当于x3,5步相当于x4，或者设acv+步数为k，那么效果是x（k-1）。
说了这么多，有什么用呢？
其实这些就是问题的本质。相当于动态规划。因为总步数一定，目的就是让这些数乘起来尽可能大。
当然这里面还掺杂了初始平A这种东西。至少得3次平A之后再使用acv。
其实有鉴于上一道题，我本来一开始想尝试数学解法，结果还是不行。看来面试的时候还是直接奔DP比较靠谱。当然有大神掏出了O（1）的数学解法，我表示牛到不行，只能佩服。后面有讲，总之数学解法难度是ACM级别的（臆测）。
DP就不同了，只要知道关系式就行。
这里的话，很明显有子问题。拿上面的形状来说：
初始若干平A + （acv+）+（acv+）...
我们可以单独把最后一个acv+拿出来，拿它的长度做文章。
设dp[i]是i步能获得的最大A数量，因为它总是以acv+结尾（假设i>=6），其长度在3~（i-3）之间。我们可以遍历这个长度，结合之前剩下的dp，来取一个最大值。也就是说

for j in xrange(3, i - 2):
    dp[i] = max(dp[i], dp[i-j]*(j-1))

更详细的解释：i指目前我们考虑的下标，j是最后acv+的长度，按照之前说的acv+长度为j，那么效果就是乘以（j-1），剩下的部分长度为i-j，之前已经算过了直接拿出来就好。要做的就是遍历长度j可能的值计算dp[i]，然后取一个最大值。

X.
https://leetcode.com/articles/4-keys-keyboard/

We either press 'A', or press 'CTRL+A', 'CTRL+C', and some number of 'CTRL+V's. Thus, in the context of making N keypresses to write the letter 'A' M times, there are only two types of moves:

• Add (1 keypress): Add 1 to M.
• Multiply (k+1 keypresses): Multiply M by k, where k >= 2.

Say best[k] is the largest number of written 'A's possible after k keypresses.

If the last move in some optimal solution of k keypresses was adding, then best[k] = best[k-1] + 1.

Otherwise, if the last move was multiplying, then we multiplied by x, and best[k-(x+1)] = best[k-(x+1)] * x for some x < k-1.

Taking the best of these candidates lets us find best[k] in terms of previous best[j], when j < k.

Time Complexity: $O(N^2)$. We have two nested for-loops, each of which do $O(N)$ work.

  public int maxA(int N) {

    int[] best = new int[N + 1];

    for (int k = 1; k <= N; ++k) {

      best[k] = best[k - 1] + 1;

      for (int x = 0; x < k - 1; ++x)

        best[k] = Math.max(best[k], best[x] * (k - x - 1));

    }

    return best[N];

  }

https://discuss.leetcode.com/topic/97721/mathematical-proof-of-the-o-n-solution

The reason we could use dp[i] = max(dp[i-4]*3, dp[i-5]*4) instead of dp[i] = max(dp[i-3]*2, dp[i-4]*3, dp[i-5]*4, dp[i-6]*5, ...) is the following property:

When i >= 6, we have 5/4 * dp[i] <= dp[i+1] <= 3/2 * dp[i].

We prove it using strong mathematical induction. Base case is trivial: dp[6] = 6, dp[7] = 9, dp[8] = 12.
Now assume 5/4 * dp[i] <= dp[i+1] <= 3/2 * dp[i] for all i >= 6 && i < n, we prove 5/4 * dp[n] <= dp[n+1] <= 3/2 * dp[n]. By the given DP formula, dp[n+1] = max(dp[n-2]*2, dp[n-3]*3, dp[n-4]*4, dp[n-5]*5, ...). We have dp[n-3]*3 >= dp[n-2]*2 because dp[i+1] <= 3/2 * dp[i] holds when i = n-3. Similarly, we have dp[n-4]*4 >= dp[n-5]*5 because dp[i+1] >= 5/4 * dp[i] holds when i = n-5.
Now the key part: for all k >= 5 && k < n, we have dp[n-4]*4 >= dp[n-k]*k i.e. dp[n-4] >= k/4 * dp[n-k] because dp[n-4] >= 5/4 * dp[n-5] >= (5/4)^2 * dp[n-6] >= ... >= (5/4)^j * dp[n-j-4]. Now let j = k-4, we get dp[n-4] >= (5/4)^(k-4) * dp[n-k] = (1 + 1/4)^(k-4) * dp[n-k] >= (1 + 1/4 * (k - 4)) * dp[n-k] = k/4 * dp[n-k], by the Bernoulli inequality. Proof complete.

(To be ultimately rigorous, I actually have to prove dp[n-5] >= k/5 * dp[n-k] and dp[n-4] >= 5/4 * dp[n-5] separately, due to the i >= 6 limit in the property. But I'd rather keep the proof simpler.)

https://discuss.leetcode.com/topic/97631/two-java-dp-solution-o-n-2-and-o-n

dp[i] = max(dp[i], dp[i-j]*(j-1)) j in [3, i)

public int maxA(int N) {
        int[] dp = new int[N+1];
        for(int i=1;i<=N;i++){
            dp[i] = i;
            for(int j=3;j<i;j++){
                dp[i] = Math.max(dp[i], dp[i-j] * (j-1));
            }
        }
        return dp[N];
    }

This one is O(n), inspired by paulalexis58. We don't have to run the second loop between [3,i). Instead, we only need to recalculate the last two steps. It's interesting to observe that dp[i - 4] * 3 and dp[i - 5] * 4 always the largest number in the series. Welcome to add your mathematics proof here.

public int maxA(int N) {
    if (N <= 6)  return N;
    int[] dp = new int[N + 1];
    for (int i = 1; i <= 6; i++) {
      dp[i] = i;
    }
    for (int i = 7; i <= N; i++) {
      dp[i] = Math.max(dp[i - 4] * 3, dp[i - 5] * 4);
      // dp[i] = Math.max(dp[i - 4] * 3, Math.max(dp[i - 5] * 4, dp[i - 6] * 5));
    }
    return dp[N];
  }

X. http://www.geeksforgeeks.org/how-to-print-maximum-number-of-a-using-given-four-keys/
a) For N < 7, the output is N itself. b) Ctrl V can be used multiple times to print current buffer (See last two examples above). The idea is to compute the optimal string length for N keystrokes by using a simple insight. The sequence of N keystrokes which produces an optimal string length will end with a suffix of Ctrl-A, a Ctrl-C, followed by only Ctrl-V's (For N > 6).
The task is to find out the break=point after which we get the above suffix of keystrokes. Definition of a breakpoint is that instance after which we need to only press Ctrl-A, Ctrl-C once and the only Ctrl-V’s afterwards to generate the optimal length. If we loop from N-3 to 1 and choose each of these values for the break-point, and compute that optimal string they would produce. Once the loop ends, we will have the maximum of the optimal lengths for various breakpoints, thereby giving us the optimal length for N keystrokes.

int findoptimal(int N)

{

    // The optimal string length is N when N is smaller than 7

    if (N <= 6)

        return N;

    // Initialize result

    int max = 0;

    // TRY ALL POSSIBLE BREAK-POINTS

    // For any keystroke N, we need to loop from N-3 keystrokes

    // back to 1 keystroke to find a breakpoint 'b' after which we

    // will have Ctrl-A, Ctrl-C and then only Ctrl-V all the way.

    int b;

    for (b=N-3; b>=1; b--)

    {

            // If the breakpoint is s at b'th keystroke then

            // the optimal string would have length

            // (n-b-1)*screen[b-1];

            int curr = (N-b-1)*findoptimal(b);

            if (curr > max)

                max = curr;

     }

     return max;

}

DP:

int findoptimal(int N)

{

    // The optimal string length is N when N is smaller than 7

    if (N <= 6)

        return N;

    // An array to store result of subproblems

    int screen[N];

    int b;  // To pick a breakpoint

    // Initializing the optimal lengths array for uptil 6 input

    // strokes.

    int n;

    for (n=1; n<=6; n++)

        screen[n-1] = n;

    // Solve all subproblems in bottom manner

    for (n=7; n<=N; n++)

    {

        // Initialize length of optimal string for n keystrokes

        screen[n-1] = 0;

        // For any keystroke n, we need to loop from n-3 keystrokes

        // back to 1 keystroke to find a breakpoint 'b' after which we

        // will have ctrl-a, ctrl-c and then only ctrl-v all the way.

        for (b=n-3; b>=1; b--)

        {

            // if the breakpoint is at b'th keystroke then

            // the optimal string would have length

            // (n-b-1)*screen[b-1];

            int curr = (n-b-1)*screen[b-1];

            if (curr > screen[n-1])

                screen[n-1] = curr;

        }

    }

    return screen[N-1];

}

http://bookshadow.com/weblog/2017/07/30/leetcode-4-keys-keyboard/

dp[z][y]表示利用z次操作，缓冲区内的字符数为y时，屏幕上打印的最大字符数

初始dp[0][0] = 0

状态转移方程：

当按下字符A时：

dp[z + 1][y] = max(dp[z + 1][y], dp[z][y] + 1)

当按下Ctrl-V时：

dp[z + 1][y] = max(dp[z + 1][y], dp[z][y] + y)

当按下Ctrl-A + Ctrl-C时：

dp[z + 2][dp[z][y]] = max(dp[z + 2][dp[z][y]], dp[z][y])

    def maxA(self, N):
        """
        :type N: int
        :rtype: int
        """
        dp = collections.defaultdict(lambda : collections.defaultdict(int))
        dp[0][0] = 0 #step, buffer
        for z in range(N):
            for y in dp[z]:
                #Key 1: (A):
                dp[z + 1][y] = max(dp[z + 1][y], dp[z][y] + 1)
                #Key 4: (Ctrl-V):
                dp[z + 1][y] = max(dp[z + 1][y], dp[z][y] + y)
                #Key 2: (Ctrl-A): + Key 3: (Ctrl-C):
                dp[z + 2][dp[z][y]] = max(dp[z + 2][dp[z][y]], dp[z][y])
        return max(dp[N].values())

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

https://www.geeksforgeeks.org/how-to-print-maximum-number-of-a-using-given-four-keys/
https://leetcode.com/articles/4-keys-keyboard/

Approach #2: Optimized Dynamic Programming [Accepted]

Intuition

If we multiply by 2N, paying a cost of 2N+1, we could instead multiply by N then 2, paying N+4. When N >= 3, we don't pay more by doing it the second way.

Similarly, if we are to multiply by 2N+1 paying 2N+2, we could instead multiply by N+1 then 2, paying N+5. Again, when N >= 3, we don't pay more doing it the second way.

Thus, we never multiply by more than 5.

Algorithm

Our approach is the same as Approach #1, except we do not consider multiplying by more than 5 in our inner loop. For brevity, we have omitted this solution.

Complexity Analysis

• Time Complexity: $O(N)$. We have two nested for-loops, but the inner loop does $O(1)$ work.
• Space Complexity: $O(N)$, the size of best.

---

Approach #3: Mathematical [Accepted]

Explanation

As in Approach #2, we never multiply by more than 5.

When N is arbitrarily large, the long run behavior of multiplying by k repeatedly is to get to the value $k^{\frac{N}{k+1}}$. Analyzing the function $k^{\frac{1}{k+1}}$ at values $k = 2, 3, 4, 5$, it attains a peak at $k = 4$. Thus, we should expect that eventually, best[K] = best[K-5] * 4.

Now, we need to make a few more deductions.

• We never add after multiplying: if we add c after multiplying by k, we should instead multiply by k+c.
• We never add after 5: If we add 1 then multiply by k to get to (x+1) * k = xk + k, we could instead multiply by k+1 to get to xk + x. Since k <= 5, we must have x <= 5 for our additions to not be dominated.
• The number of multiplications by 2, 3, or 5 is bounded.
• Every time we've multiplied by 2 two times, we prefer to multiply by 4 once for less cost. (4^1 for a cost of 5, vs 2^2 for a cost of 6.)
• Every time we've multiplied by 3 five times, we prefer to multiply by 4 four times for the same cost but a larger result. (4^4 > 3^5, and cost is 20.)
• Every time we've multiplied by 5 five times, we prefer to multiply by 4 six times for the same cost but a larger result. (4^6 > 5^5, and cost is 30.)

Together, this shows there are at most 5 additions and 9 multiplications by a number that isn't 4.

We can find the first 14 operations on 1 by hand: 1, 2, 3, 4, 5, 6, 9, 12, 16, 20, 27, 36, 48, 64, 81. After that, every subsequent number is achieved by multiplying by 4: ie., best[K] = best[K-5] * 4.

  public int maxA(int N) {

    int[] best = new int[] { 0, 1, 2, 3, 4, 5, 6, 9, 12, 16, 20, 27, 36, 48, 64, 81 };

    int q = N > 15 ? (N - 11) / 5 : 0;

    return best[N - 5 * q] << 2 * q;

  }

X. Math
https://www.jianshu.com/p/ee57e9ae02e5

然后是数学解法，参加一亩三分地的帖子。
还是回到上面的动态规划那里，转化为如下动态规划问题：

已知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
这里需要解释一下。结论就是优先使用4作为乘数，其次用3.
为什么？这里有一个“贡献因子”的理论，也就是说长度为x贡献x-1的乘数，贡献因子是(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，反映到乘数里面就是优先用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组成。
然后呢？就看不懂了……
又想了一下，这个意思应该是把平A也假设成为3或者4，否则结果里面没有说不过去。
那为什么只是N+1= 4 * n3 + 5 * n4呢？
因为作者把平A也归纳到n里面去了！换言之，作者把x0转化当成了一个acv+！
想想无论是平A=3还是4，就乘积效果而言相比acv+，都是省1步的！
所以这么写更好理解：N = 4 * n3 + 5 * n4 - 1
之后就一切自然而然了，然而还有一个特例就是10不遵守这个条件……
作者原话是：

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也超了，所以不成立。反映到计算就是n4=-1.
总而言之，这个算法充满神奇，多个大胆的假设，然后最后还是对的。临场还是别抱数学解法的想法吧……
彩蛋：一个基于数学解法的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是否有特别含义，对我而言这是滚动DP，按道理3个格子够用了？
想一想，i=7的时候需要dp[2]和dp[3]的值，为了不冲突，所以把值放到dp[1]，很合理的解释。
试了一下，把所有%6改成%7，结果不变，说明我的猜测是正确的。事实上可以单独拿3个格子出来装，不过牵涉到初始值的问题麻烦一点。
另外dp = range(N + 1)改成dp = range(7)也不会有任何问题。