651.4 Keys Keyboard

1-DP

https://leetcode.com/problems/4-keys-keyboard/discuss/105980/

要想N步生成最多个A，可在N-2步的时候，Ctrl A，N-1步的时候，Ctrl C，第N步的时候Ctrl V，这样就能将N-3步生成的A的个数，翻倍。

如何确定在第几步Ctrl A，然后再Ctrl C、Ctrl V呢，需要依次判断第i-3步之前的步骤。

得到递推公式 dp[i] = max(dp[i],dp[i-j-1]);dp[i]表示第i步生成的最多的A的个数。http://www.cnblogs.com/hellowooorld/p/7264961.html

http://www.cnblogs.com/hellowooorld/p/7264961.html

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 j = 0; j <= i - 3; j++){
                dp[i] = Math.max(dp[i], dp[j] * (i - j - 2 + 1));
            }
        }
        return dp[N];
    }
}