# Java 4 lines recursion, with step-by-step explanation to derive DP

• We use `i` steps to reach `maxA(i)` then use the remaining `n - i` steps to reach `n - i - 1` copies of `maxA(i)`

For example:
A, A, A, Ctrl A, Ctrl C, Ctrl V, Ctrl V
Here we have `n = 7` and we used `i = 3` steps to reach `AAA`
Then we use the remaining `n - i = 4` steps: Ctrl A, Ctrl C, Ctrl V, Ctrl V, to reach `n - i - 1 = 3` copies of `AAA`

We either don't make copies at all, in which case the answer is just `n`, or if we want to make copies, we need to have 3 steps reserved for Ctrl A, Ctrl C, Ctrl V so `i` can be at most `n - 3`

``````    public int maxA(int n) {
int max = n;
for (int i = 1; i <= n - 3; i++)
max = Math.max(max, maxA(i) * (n - i - 1));
return max;
}
``````

Now making it a DP where `dp[i]` is the solution to sub-problem `maxA(i)`

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

• The inner loop of the bottom-up DP can be truncated to at most four terms, that is, for `dp[i]`, we only need to choose the largest one from `dp[i - 3] * 2, dp[i - 4] * 3, dp[i - 5] * 4, dp[i - 6] * 5`, while all the rest terms like `dp[i - 7] * 6, dp[i - 8] * 7, ...` can be ignored. The reason is as follows: when computing `dp[i - 3]`, we've already chosen its value to be the maximum of terms like `dp[i - 6] * 2, dp[i - 7] * 3, dp[i - 8] * 4, ...`, which implies `dp[i - 3] >= dp[i - k] * (k - 4)` for `k >= 6`. This further leads to `dp[i - 3] * 2 >= dp[i - k] * (2k - 8) >= dp[i - k] * (k - 1)` if `k >= 7`. So we always have `dp[i - 3] * 2 >= dp[i - 7] * 6, dp[i - 3] * 2 >= dp[i - 8] * 7, ...`. Therefore terms like `dp[i - 7] * 6, dp[i - 8] * 7, ...` won't contribute when evaluating `dp[i]`.

The truncation will make the DP solution run effectively in `O(n)` time. Also the space complexity can be reduced to `O(1)` since now we only need to maintain a constant number of variables (seven, I would say, `dp[i], dp[i-1], dp[i-2], dp[i-3], dp[i-4], dp[i-5], dp[i-6]`). The following is the modified code:

``````public int maxA(int N) {
int[] dp = new int[7];

for (int i = 1; i <= N; i++) {
dp[0] = i;

for (int k = 6; k > 2; k--) {
dp[0] = Math.max(dp[0], dp[k] * (k - 1));
}

for (int k = 6; k > 0; k--) {
dp[k] = dp[k - 1];
}
}

return dp[0];
}
``````

• Can anyone explain why n-i-1 represents copies of maxA(i)? Like what's the math behind this?

• @jyc123 Why n-i-1 represents copies of maxA(i)? Because after you use i steps to reach maxA(i), you still have n -i steps. then you cost 2 more steps to do Ctrl-A and Ctrl-C, After this you have n-i-2 steps left, all the rest could be used to do Ctrl-V, so you increase n-i-2 copies, at last, you have the original copy, you need add it to the total num of copies. therefore, you have n-i-1 copies

• @wxl163530 Very clear explanation. Thx!

• Hi, Thank you for your sharing! Could you please give a proof why multiple use of Key2 won't comes more 'A's than one time usage?

• @fun4LeetCode
Hi, could you please explain why should we consider all last 6 results not the last 3 results? Thank you so much!

• @AmyXyy Hi AmyXyy. I actually saw some people propose that we only need to consider the second, third and fourth ones. But there is no easy way to prove that. Considering the middle three results or all six results does not make a difference regarding the time complexity, though the former may be more efficient for large N.

• @jyc123
it is actually (n - i - 2 + 1)
2 is (ctrl A and ctrl C)
n - i - 2 is how many times of the (ctrl v)
+1 is you need to count the been copied original one

• ``````    public int maxA(int n) {
int[] dp = new int[n + 1];
for (int i = 0; i <= n; i++) {
dp[i] = i; // I feel like dp[i] = dp[i - 1] + 1 is more reasonable
// because dp[i] might come from ..., ..., CTRL-V then append an A
// even though we can prove it's impossible
for (int j = 1; j <= i - 3; j++)
dp[i] = Math.max(dp[i], dp[j] * (i - j - 1));
}
return dp[n];
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.