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

解法

方法一：动态规划

思考

四个按键含全选与复制，最优序列几乎总是「输入若干 A，再反复粘贴」。穷举按键串长度为 \(n\le 50\) 尚可，但状态可用 DP 压掉。

\(dp[i]\) 为 \(i\) 次按键的最大 A 数。要么全按 A 得 \(i\)，要么在 \(j\) 处 Ctrl-A，此后粘贴 \(i-j\) 次，得到 \(dp[j-1]\times(i-j)\)。

定义 \(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)\)。

Python3JavaC++Go

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]

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

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

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

651. 四个键的键盘 🔒

题目描述

解法

方法一：动态规划

评论