Ok guys so i was trying to solve this problem : https://www.spoj.com/problems/HIST2/
It required DP+Bitmasks as the constraints were low N<=15
So the initial DP state i came up with was:
dp[mask] denotes the maximum perimeter for the subset of the rectangles picked by "mask"
( for ex if my heights were {1,2,3,4} and mask=0110 dp[mask] contains maximum possible perimeter for the subset {2,3})
This approach gave me the answer for maximum perimeter however while solving the problem of number of such maximal perimeters it failed to work . Which was when i noticed that an optimal solution for the above subset was 2,3,1,4 which gave a perimeter of 20 but the optimal solution for the subset {1,2,3} was the arrangement 2,1,3 or 3,1,2 , so what i’ve concluded is that a optimal solution is obtained from a non-optimal one which is why my dp state failed to count such subsets
When i researched a little bit online i found many others using the dp state :
dp[X][i] where X=mask and i=last element placed
This state seemed to work properly though.
Now my question is:
even though my dp state found the maximum perimeter it failed to find count of such maximal perimeters, Why? What is wrong in my framing or understanding of framing dp states?