LeetCode 651. 4键键盘（DP，Ctrl+CV）

Key 1: (A)：在屏幕上打印一个 'A'。

Key 2: (Ctrl-A)：选中整个屏幕。

Key 3: (Ctrl-C)：复制选中区域到缓冲区。

Key 4: (Ctrl-V)：将缓冲区内容输出到上次输入的结束位置，并显示在屏幕上。

样例 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
结果不会超过 32 位有符号整数范围。

class Solution {
public:
    int maxA(int N) {
    	vector<int> dp(N+1,0);
    	//dp[i] 表示，第 i 次按下键的最多A个数
    	for(int i = 1, j; i <= N; ++i)
    	{
    		dp[i] = max(dp[i], dp[i-1]+1);//按下A键
    		for(j = 0; j <= i-2; ++j)
    		//从前面可以的地方选一次进行ACV，后面一直V...
    		// -2 表示 AC的少了2次，后面可以一直粘（i-j-2）次 + 原来自己一次
    			dp[i] = max(dp[i], dp[j]*(i-j-1));
    	}
    	return dp[N];
    }
};