---
# System prepended metadata

title: 0651. 4 Keys Keyboard
tags: [Leetcode, Dynamic Programming, Medium]

---

# 0651. 4 Keys Keyboard
###### tags: `Leetcode` `Medium` `Dynamic Programming`
Link: https://leetcode.com/problems/4-keys-keyboard/
## 思路
dp[i]表示在i次操作之后最多能有多少个A
初始值肯定设成i
然后我们在i的前面找j
i一定要大于等于3+j 才能完整ctrl v操作
所以```dp[i] = Math.max(dp[i], dp[j]*(1+i-3-j+1))```
第一个1是头三次操作里面涵盖的一次ctrl v
i-3-j+1是后面多的ctrl v的次数
## Code
```java=
class Solution {
    public int maxA(int n) {
        int[] dp = new int[n+1];
        for(int i=0; i<=n; i++) dp[i]=i;
        for(int i=2; i<=n; i++){
            for(int j=1; j<=i-3; j++){
                dp[i] = Math.max(dp[i], dp[j]*(1+i-3-j+1));
            }
        }
        return dp[n];
    }
}
```