I participated in google apactest Round B. I was unable to solve this problem for large input. Can anyone explain how to solve it:
Let us say we are trying to remove three numbers of the array at positions ‘x’, ‘y’, ‘z’. Now this is only possible if a[x] = a[y] - k and a[y] = a[z] - k (a is the given array) and also all the numbers a[x+1], a[x+2], a[x+3]…a[y-2], a[y-1] and a[y+1], a[y+2]…a[z-2], a[z-1] are removed before because the three numbers x, y, z should be adjacent while removing.
Now let us form a DP array pos[i][j] which is a boolean array which stores the boolean value if we can remove the contiguous elements in the array a from index ‘i’ to index ‘j’ completely ?
The pos array can be computed recursively using the conditions mentioned above. And now how to calculate the final answer using pos array?
We have to make another DP array dp where dp[i] stores what is the minimum number of elements that can be achieved if we are only considering the elements a[i], a[i+1], a[i+2]…a[n-1, a[n]. This can also be constructed recursively with conditions : for all ‘j’ for which we can remove the all numbers between indexes ‘i’ and ‘j’, i.e, pos[i][j] is true, dp[i] = min(dp[i], dp[j]). The initial value dp[i] can be dp[i+1] + 1 which is the value if we are not removing a[i] at all.
Our final answer will be in dp.