While practicing DP problems on various sites, I came across this problem:- https://www.hackerearth.com/practice/algorithms/dynamic-programming/introduction-to-dynamic-programming-1/practice-problems/algorithm/leaf-and-limelight-attack-circuit/description/ on HackerEarth.
According to the editorial, we pre-process the values in the solution. Queries are divided into even and odd. DP[i] gives the solution for ith query. So, DP[1] = 1, DP[3] = 25, DP[5] = 101.
So, they have derived a formula which is :-
DP[i] = DP[i-2] + (i-2)2 + (i-1) + (i-2)2 + 2(i-1) + (i-2)2 + 3(i-1) + (i-2)2 + 4(i-1) which gets reduced to
DP[i] = DP[i-2] + 4i2 — 6*(i-1)
So my question is, how was this formula derived? What was the approach in deriving this ?
If you already know the value of DP[i], then you can easily calculate the value of DP[i + 2].
The last number of an i * i square will be i2 and it will be located in a corner. To expand the square, you will make i - 1 steps to the next corner, then another i - 1 steps to the next one, and so on, so you can express DP[i + 2] = DP[i] + i2 + i - 1 + i2 + 2(i - 1) + i2 + 3(i - 1) + i2 + 4(i - 1) = DP[i] + 4i2 + 10(i - 1).
The formula is different because I calculated i + 2 from i instead of calculating i from i - 2, but it's the same principle.