2022-03-14：一开始屏幕上什么也没有，粘贴板里什么也没有， 你只能在键盘上做如下

2022-03-14：一开始屏幕上什么也没有，粘贴板里什么也没有， 你只能在键盘上做如下4种操作中的1种： 输入：在屏幕上已经显示内容的后面加一个A， 全选：把屏幕上已经显示的全部内容选中， 复制：被选中的内容复制进粘贴板， 粘贴：在屏幕上已经显示内容的后面添加粘贴板里的内容， 给定一个正数n，表示你能操作的步数， 返回n步内你能让最多多少个A显示在屏幕上。

答案2022-03-14：

可以证明： 来到i的时候，包括i在内最多有连续4次粘贴行为 不可能更多，如果有连续5次粘贴，一定就不再是最优解 假设开始时，A的数量为S，看如下的变化过程，我们称这是行为一： 开始 全选 复制(粘贴板S个A) 粘贴 粘贴 粘贴 粘贴 粘贴 S S S 2S 3S 4S 5S 6S 但是，注意看如下的行为二： 开始 全选 复制(粘贴板S个A) 粘贴 全选 复制(粘贴板2S个A) 粘贴 粘贴 S S S 2S 2S 2S 4S 6S 行为一，经历8步，最后是6S个A 行为二，经历8步，最后是6S个A 但是行为二在粘贴板上有2S个A，而行为一在粘贴板上有S个A 所以行为一没有行为二优 以此说明：来到i的时候，包括i在内最多有连续4次粘贴行为 那么就尝试：连续1次、连续2次、连续3次、连续4次粘贴行为即可

代码用golang编写。代码如下：

package main

import "fmt"

func main() {
	ret := maxA(8)
	fmt.Println(ret)
}

func maxA(n int) int {
	// dp[0] 1步以内的最优解
	// dp[1] 2步以内的最优解
	// dp[2] 3步以内的最优解
	// dp[i] i+1步以内的最优解
	dp := make([]int, n)
	for i := 0; i < 6 && i < n; i++ {
		dp[i] = i + 1
	}
	for i := 6; i < n; i++ {
		dp[i] = getMax(getMax(dp[i-3]*2, dp[i-4]*3), getMax(dp[i-5]*4, dp[i-6]*5))
	}
	return dp[n-1]
}

func getMax(a, b int) int {
	if a > b {
		return a
	} else {
		return b
	}
}

执行结果如下：

左神java代码