README.md

comments	difficulty	edit_url	tags
true	中等	https://github.com/doocs/leetcode/edit/main/solution/0600-0699/0651.4%20Keys%20Keyboard/README.md	数学 动态规划

651. 四个键的键盘 🔒

English Version

题目描述

假设你有一个特殊的键盘包含下面的按键：

• A：在屏幕上打印一个 'A'。
• Ctrl-A：选中整个屏幕。
• Ctrl-C：复制选中区域到缓冲区。
• Ctrl-V：将缓冲区内容输出到上次输入的结束位置，并显示在屏幕上。

现在，你可以 最多 按键 n 次（使用上述四种按键），返回屏幕上最多可以显示 'A' 的个数 。

 

示例 1:

输入: n = 3
输出: 3
解释: 
我们最多可以在屏幕上显示三个'A'通过如下顺序按键：
A, A, A

示例 2:

输入: n = 7
输出: 9
解释: 
我们最多可以在屏幕上显示九个'A'通过如下顺序按键：
A, A, A, Ctrl A, Ctrl C, Ctrl V, Ctrl V

 

提示:

• 1 <= n <= 50

解法

方法一：动态规划

定义 $dp[i]$ 表示前 $i$ 个按键可以显示的最大个数。

我们可以发现，要显示最多的 A，要么一直按 A，要么以 Ctrl-V 结束。

• 一直按 A 的情况，满足 $dp[i] = i$。
• 以 Ctrl-V 结束的情况，我们枚举对应的 Ctrl-A 的位置 $j$，可以得到 $dp[i]=max(dp[i], dp[j-1] \times (i - j))$。

时间复杂度 $O(n^2)$，空间复杂度 $O(n)$。

Python3

class Solution:
    def maxA(self, n: int) -> int:
        dp = list(range(n + 1))
        for i in range(3, n + 1):
            for j in range(2, i - 1):
                dp[i] = max(dp[i], dp[j - 1] * (i - j))
        return dp[-1]

Java

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

C++

class Solution {
public:
    int maxA(int n) {
        vector<int> dp(n + 1);
        iota(dp.begin(), dp.end(), 0);
        for (int i = 3; i < n + 1; ++i) {
            for (int j = 2; j < i - 1; ++j) {
                dp[i] = max(dp[i], dp[j - 1] * (i - j));
            }
        }
        return dp[n];
    }
};

Go

func maxA(n int) int {
	dp := make([]int, n+1)
	for i := range dp {
		dp[i] = i
	}
	for i := 3; i < n+1; i++ {
		for j := 2; j < i-1; j++ {
			dp[i] = max(dp[i], dp[j-1]*(i-j))
		}
	}
	return dp[n]
}