题目描述：

LeetCode 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.

题目大意：

有下列四种操作：

Key 1: (A): 在屏幕上打印'A'

Key 2: (Ctrl-A): 全选

Key 3: (Ctrl-C): 将选中内容复制到缓冲区

Key 4: (Ctrl-V): 将缓冲区内容粘贴在屏幕上

给定操作次数N，求最多可以打印的字符数。

解题思路：

动态规划（Dynamic Programming）

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])

Python代码：

class Solution(object):
    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())

 

本文链接：http://bookshadow.com/weblog/2017/07/30/leetcode-4-keys-keyboard/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码