FourKeyKeyboard [source code]

public class FourKeyKeyboard {
static
/******************************************************************************/
public class Solution {
    public int maxA(int N) {
        if (N <= 6)
            return N;
        int[] memo = new int[N + 1];
        for (int i = 0; i <= 6; i++)
            memo[i] = i; 
        for (int i = 7; i <= N; i++) {
            memo[i] = i;
            for (int j = 1; j <= i - 3; j++)
                memo[i] = Math.max(memo[i], memo[j] * (i - j - 1));
        }
        return memo[N];
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        FourKeyKeyboard.Solution tester = new FourKeyKeyboard.Solution();
    }
}

首先肯定还是尝试从笨办法开始想, 人逻辑做做看, 尤其是这个题目也是给了很多例子的; 刚开始写了这个算法:

public class Solution {  
    public int maxA(int N) {  
        if (N <= 3)  
            return N;  
        int sum = N - 2, mid = sum / 2;  
        return Math.max(N, mid * (sum - mid) + (sum + 1) / 2);  
    }  
}

但是这个算法是不对的, 这个算法其实是假定我们只有一个AC操作, 但是这个想法肯定是不对的; 现在我们的一个uncertainty就是, 我们其实可以插入多个AC的combo;

这个题目也算是一个最值搜索的问题, 一般碰到最值搜索的问题, 我们也说过, 两个思路方向:

deterministic search (including greedy)
DP

这个题目在做的过程中其实感觉到一点DP的影子了, 比如对于一个N等于4的问题, 你当然可以1234这样的按键组合, 但是这样最后只能输出2, 还不如直接1111的组合; 所以这里其实就出现了一个decision的概念: 虽然你当前的N可能足够支撑你插入一个AC(CtrlA+CtrlC)的combo, 但是是否值得呢? 这个根据具体的problem size有不同的结论;

但是也就能想到这么多了, 具体怎么设定这个DP其实还是一点想法都没有; 看答案了;

尽管这个问题最后没有做出来, 我这里还是对今后自己做题提出一个要求:

看答案之前最起码timer上憋30分钟. 我知道这三十分钟很难受, 但是如果自己一点没有agonize过的题目, 真的是跟没做过完全没有区别的. 就30分钟, 这个要求其实不过分;
从笨办法, 人逻辑开始做, 举例子, 简单升级, relaxation, 能想多少是多少; 任何一个当时看起来fruitless的想法, 日后都有可能成为帮助你记忆或者深入理解这个算法的关键;

关于表格的长度还是有一点需要强调, 很多时候需要做到N+1, 因为这个N很多时候是1-based的; 如果我们希望能够直接用1-based的方式来查这个表, 那么长度+1是最省事的办法; 当然这个同时也让DP的base case更加明确;

最后写出来的是一个N^2的版本, 因为我感觉这个解法才是这个问题最核心的解法, 至于后面降低fanning的优化, 不用急着直接一步头就写出来, 也太假了;

最后的速度是9ms (11%), 还是可以理解的, 毕竟有降低fanning的解法, 还有数学解法;

这个是discussion最优解(不是最终版本, 还没有加memo):

public class Solution {  
    public int maxA(int n) {  
        int max = n;  
        for (int i = 1; i <= n - 3; i++)  
            max = Math.max(max, maxA(i) * (n - i - 1));  
        return max;  
    }  
}

所以这个问题我还是想的太简单了, 这个问题其实属于DP里面的搜索空间比较大的一个了(每一个level的fanning factor是n, 而不是以前常见的只有1,2,3这么小的);

这个算法看起来很像我自己的错误算法: 都是表示在当前level只做一次翻倍, 然后decision的内容就是where to do the ACV combo. 但是我的算法的错误的地方在于, 我认为翻倍之前的按键全都是1, 也就是全都是单击. 但是这里这个想法不同, 这里认为翻倍之前的数量应该有一个全新的level call来决定;

我感觉这个问题暴露出来我现在对于DP还是没有彻底的理解: 即使是像这题这样已经用tag告诉我了说这个问题可以用DP, 我还是想不到正确的DP算法; 我在想的时候更多的还是有点类似在套用模板, 把这个问题往一个题型的模板里面套, 但是本身并没有掌握一个真正让自己的脑子主动调用DP思路的精髓, 也就是脑子里还没有真正养成一个, 比如我看到什么特点的题目, 我就本能的知道这里应该用DP, 而且我还知道应该怎么把DP用在这里;

我之前思考的时候的一个直觉是对的, 这个问题的难点是我们不知道到底有多少个翻倍操作, 这是一个uncertainty; 甚至, 就算是退一万步, 我们真的知道了有多少个翻倍操作, 我们也不知道它们具体的安排的位置; 这个好像有一个chain, 然后我们要在其中安排几个ball, 但是我们不知道这些ball正确的摆放位置一样; 这种visual模型以前是不是好像见过? 事实上应该能想到这种模型用DP的; 就从最后一个ball的位置开始思考, 用Top-Down的方式一直往下开展就行了;

这个是加了memo的版本:

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

完整的作者自己的解释:
@yuxiangmusic said in Java 4 lines recursion, with step-by-step explanation to derive DP:

We use i steps to reach maxA(i) then use the remaining n - i steps to reach n - i - 1 copies of maxA(i)

For example:
A, A, A, Ctrl A, Ctrl C, Ctrl V, Ctrl V
Here we have n = 7 and we used i = 3 steps to reach AAA
Then we use the remaining n - i = 4 steps: Ctrl A, Ctrl C, Ctrl V, Ctrl V, to reach n - i - 1 = 3 copies of AAA

We either don't make copies at all, in which case the answer is just n, or if we want to make copies, we need to have 3 steps reserved for Ctrl A, Ctrl C, Ctrl V so i can be at most n - 3

注意看他这里第二个其实是一个Bottom-Up的写法, 但是这俄格写法其实是N^2而不是N的算法;

The inner loop of the bottom-up DP can be truncated to at most four terms, that is, for dp[i], we only need to choose the largest one from dp[i - 3] * 2, dp[i - 4] * 3, dp[i - 5] * 4, dp[i - 6] * 5, while all the rest terms like dp[i - 7] * 6, dp[i - 8] * 7, ... can be ignored. The reason is as follows: when computing dp[i - 3], we've already chosen its value to be the maximum of terms like dp[i - 6] * 2, dp[i - 7] * 3, dp[i - 8] * 4, ..., which implies dp[i - 3] >= dp[i - k] * (k - 4) for k >= 6. This further leads to dp[i - 3] * 2 >= dp[i - k] * (2k - 8) >= dp[i - k] * (k - 1) if k >= 7. So we always have dp[i - 3] * 2 >= dp[i - 7] * 6, dp[i - 3] * 2 >= dp[i - 8] * 7, .... Therefore terms like dp[i - 7] * 6, dp[i - 8] * 7, ... won't contribute when evaluating dp[i].

The truncation will make the DP solution run effectively in O(n) time. Also the space complexity can be reduced to O(1) since now we only need to maintain a constant number of variables (seven, I would say, dp[i], dp[i-1], dp[i-2], dp[i-3], dp[i-4], dp[i-5], dp[i-6]).

public int maxA(int N) {  
    int[] dp = new int[7];  

    for (int i = 1; i <= N; i++) {  
        dp[0] = i;  

        for (int k = 6; k > 2; k--) {  
            dp[0] = Math.max(dp[0], dp[k] * (k - 1));  
        }  

        for (int k = 6; k > 0; k--) {  
            dp[k] = dp[k - 1];  
        }  
    }  

    return dp[0];  
}

这个是一个O(N)的做法, 主要的技巧就是改善memo/cache的方式. 在以前fanning比较小的题目里面, 这种优化往往被视为为了节省空间的小噱头. 但是在这个fanning很大的题目里面, 居然对时间的提升也起到关键的效果;

严格来说这里这个优化其实并不是之前那种纯粹为了改善空间复杂度的小优化: 那种优化, 其实是没有改变fanning的; 但是这里这个优化, 其实是通过自己主动的分析, 将fanning从N降低到了4. 至于得到的空间复杂度的优化(只需要维护7个变量), 只是一个附加产品: 当你知道fanning很小之后, 自然而言的就可以改善空间复杂度了;

他这里这个降低fanning的原理, 刚开始以为很trivial, 仔细看了一下, 其实还是挺巧妙的;

另外注意他改善memo的写法: 虽然说是要七个, 实际上有用的是6个, 严格来说这里的fanning是6, 然后第七个其实就是用来计算当前level的一个buffer; 另外注意他这里对这七个变量的组织方式: 放在一个数组里面. 这样每一个level计算完了之后, shift起来代码写起来很方便; 然后另外一点是他这个index其实是倒过来的, 严格来说dp[k]里面保存的其实是[i-k]的结果. dp[0]自然也就是直接用来计算max(i)的buffer了;

其实为了节省空间, 这里时间上还是有Trade-Off的; 每一个level都要做一次shift, 这个速度占用还是摆在那里的;

下面有人提出, 其实这个fanning还可以进一步降低:

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];  
}

另外提一个小问题, 比如我们算[8]的解的时候, 我们就考虑在[1]..[5]位置之后立刻开始翻倍, 然后选择一个最大值. 但是你想过一个问题没有, 有没有可能实际上, 比如在某一个i的max之后, 不翻倍其实才能获得最大值呢? 这个是一个uncertainty, 但是其实是一个很好排除的uncertainty: 我们讨论的i的范围, 都是能够保证有足够的空间, 在max(i)之后至少能进行一次翻倍; 比如有一个max(i), 然后我们至少能在之后进行依此翻倍, 意思就是这个i之后我们至少还能继续再来三个按键; 那么假如max(i)之后我们直接三个1, 那么最后得到的结果是max(i) + 3. 但是如果我们max(i)之后一个翻倍, 得到的是2 * max(i). 前者会胜出的唯一可能性就是当max(i) < 3的时候, 而这样的i其实只有0, 1, 2三个. 所以在后面更general的情况下的时候, 这个问题是不用考虑的; 你当前level的decision, 就是一定会发生一个翻倍, 你考虑的就是翻倍的位置. 至于是否应该翻倍, 不要去怀疑, 一定是应该去翻倍, as long as you got the space;

另外关于这里两个最大项的证明在这个帖子里面并没有人给出;

这个题目很新, 不过居然有人已经想出来O(1)的math解法了:

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

Pure math. This problem is to partition number N into 3's and 4's and get their product. n = N / 5 + 1 is 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.

拿到一个别人写的算法, 看不懂, 其实还是很正常的事情, 这个时候该做的, 还是自己写一个例子出来, 然后看看what the algorithm does to this input;

code vs computation

你拿到的是一个code, 跟真正本质下面的algorithm之间还是有一层理解的差距. 要想真正理解这个code, 最好的方法, 就是拿到一个例子, 然后自己跑一下, 看看这些循环啊, conditional啊, 背后藏着的到底是什么样的computation, 这样才能真正理解这个code背后的算法思想;

话虽然这么说, 这个题目看了半天还是没有理解背后的原理; 地里发了帖子问人, 然后discussion里本来的帖子也watch了, 看看后面有没有其他人提供更好的解释;

这个题目非常新, 才出来不到一个月, 就有人想出这么多这些解法了, 还是挺神奇的;

这个是另外一个帖子里面关于DP的优化的证明:

We can solve this problem using DP with optimization in O(N) time, based on two observations. Here I assume n >= 6.
1) For dp[n], we can copy dp[n-3] and paste 1 time, or copy dp[n-4] and paste 2 times, and so on.
So dp[n] = max(dp[n-i]x(i-1), for i >= 3 && i <= n-1); This will result in an O(N^2) solution.
2) However, when i >= 7, i-3 is the same or more optimal than i. The reason is that we can select, copy and paste 1 time, then select, copy and keep pasting, dp[n] = dp[n-i]x2x(i-4). 2(i-4) >= i-1 when i >= 7.
So only i = 3, 4, 5, 6 are considered.

这个证明的就是当你计算dp[n]的时候, 只需要考虑dp[n-3]..dp[n-6], 这个跟一开始那个最优解里面的证明思路其实是类似的. 另外上面那个另外一个帖子, 最后得出结论dp[n-3]和dp[n-6]也可以不用考虑, 这个在这里也没有得到证明;

关于这个fanning等于2的证明, 这里有一个:
@Spin0za said in 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.)

这个其实就是标准的CS问题的证明, 来一个proposition, 然后induction证明; 难点肯定还是得到这个proposition的过程(如果太弱, 不足以在termination证明你最后想要的结论, 如果这个proposition/lemma太强, 最后很可能就无法证明). 这个induction证明的具体过程我就没有细看了, 大概知道意思就行了; 对于这个问题, 能够学会把fanning降低到4就已经很足够了;

另外这个题目还有人直接用一个DFS写了, 当然是加了pruning和cache的:

class Solution {  
    func maxA(_ N: Int) -> Int {  
        var result = Int.min  
        var cache = Set<String>()  

        helper(N, 1, 0, 1, &result, &cache)  

        return result          
    }  

    fileprivate func helper(_ N: Int, _ steps: Int, _ buffer: Int, _ candidate: Int, _ result: inout Int, _ cache: inout Set<String>) {  
        if steps > N {  
            return  
        }  
        if steps == N {  
            result = max(result, candidate)  
            return  
        }  

        if cache.contains("\(candidate):\(buffer):\(steps)") {  
            return  
        }  

        if buffer > 1 {  
            // Paste  
            helper(N, steps + 1, buffer, candidate + buffer, &result, &cache)  
        } else {  
            // Print  
            helper(N, steps + 1, buffer, candidate + 1, &result, &cache)  
        }  
        // Select + Copy + Paste  
        helper(N, steps + 3, candidate, candidate * 2, &result, &cache)  

        cache.insert("\(candidate):\(buffer):\(steps)")  
    }  
}

不过是用swift写的, 暂时有点看不懂, 先摆着不管了;

Problem 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 <= N <= 50
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

LC651 FourKeyKeyboard

FourKeyKeyboard [source code]

code vs computation

Problem Description

results matching ""

No results matching ""