跳转至

651. 四个键的键盘 🔒

题目描述

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

  • 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)$。

1
2
3
4
5
6
7
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]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
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];
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
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];
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
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]
}

评论