What is wrong in my understanding of formation of DP-states?

general
1

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?

2

I don’t believe your original formulation of dp[mask] is correct because just mask is insufficient to form the recurrence. If you share your code/algorithm it will be easier to analyze.

3

Hey , but for just the maximum perimeter dp[mask] worked fine .
Here’s the code for my solution : https://pastebin.com/vBfCiK3c
So basically what i’ve done is for each mask ive calculated what the maximum perimeter possible is and i’ve stored the possibilities of last rectangle heights in set. And ive kept count of how many such maximal perimeters end with a certain last rectangle for a given rectangle height. So this is basically my problem , my dp state works for maximal perimeter but doesn’t work for no of such maximal perimeters.So…does that mean my dp state formation is wrong?