Hello everyone, i am trying to learn divide and conquer DP optimizations from here . Clearly to apply optimization A[i][j] <= A[i][j+1] . Now i want to ask how would i know whether this condition is fulfilled without generating its values from brute force method .
This is probably problem specific, that is, you have to find out what A[i][j] means in the problem and try to justify whether the given condition makes sense or not.
However, this won’t always be easy. You can instead run both the optimisation and the original algorithm on some random test data and see if they give the same value.
1 Like
Thanks for the reply,
Actually for the problem CCC from the recent long challenge i did compared the result from brute dp and optimized one, but wasn’t able to find any case 
.