651. 4键键盘

原题地址：https://leetcode.cn/problems/4-keys-keyboard/

题解

首先，我们考虑到输入一个A这个操作每次只能带来一个A的收益，而Ctrl+V能够带来整个缓冲区的收益，在n达到一个阈值后，我们只需要循环地执行一个Ctrl+A更新缓冲区后若干次Ctrl+V的操作即可，不再需要进行输入A的操作，可以发现，这个阈值为6，即从第六次操作之后，我们就再也不需要单独输入一个A了，这样我们需要考虑的情况实际上只有这次操作需要Ctrl+A+C还是Ctrl+V，即一个Ctrl+A+C+n*V的循环

我们设dp[i][0]为在第i次操作单独输入一个A，dp[i][1]为在第i次操作更新缓冲区，dp[i][2]为在第i次操作不更新缓冲区三种情况下的最大字符数量

对于dp[i][0]而言：

由于dp[i][0]在i>5后我们就再也不会用到了，实际上这里不需要进行过多的比较，在i=0~5时分别等于i即可

对于dp[i][1]而言：

由于在第i次操作更新了缓冲区，自然地，我们在第i次操作Ctrl+V，第i-1次操作Ctrl+C，第i-2次操作Ctrl+A，那么我们全选的A的数量实际上是第i-3次的操作下A的数量，由于我们希望缓冲区尽可能抵达，因此在第i-3次操作下比较单独输入A和Ctrl+V（我们不可能连续两次Ctrl+A+C，这样是稳亏不赚的）取较大值，此时字符A的数量为这个较大值的二倍（原本的数量+缓冲区的一份副本）

对于dp[i][2]而言：

由于我们在这次操作中不更新缓冲区，那么一定是在0i-1的某一次操作中进行了Ctrl+A+C，并一路重复Ctrl+V到第i次操作（不考虑在中间再次Ctrl+A+C的情况，因为这种情况本质上是拆分成了两轮Ctrl+A+C+n*V的操作），我们用j枚举3i-1，其中对于第j次操作更新缓冲区，复制的内容的第j-3次的字符数量（同上，要在第j-3次操作下取较大值），其中从j到i一共进行了i-j次操作，这时的dp[i][2]为

$，其中$

时间复杂度：O(N^2)

空间复杂度：O(N)

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

class Solution {
    fun maxA(n: Int): Int {
        val dp = Array(n) { IntArray(3) }
        dp[0][0] = 1
        for (i in 1 until n) {
            dp[i][0] = dp[i - 1][0] + 1
            if (i >= 3) {
                dp[i][1] = maxOf(dp[i - 3][0], dp[i - 3][2]) * 2
                for (j in 3 until i) {
                    dp[i][2] = maxOf(dp[i][2], dp[j][1] + maxOf(dp[j - 3][0], dp[j - 3][2]) * (i - j))
                }
            }
        }
        return maxOf(dp[n - 1][0], dp[n - 1][1], dp[n - 1][2])
    }
}