Can anyone explain how does this ques involve overlapping subproblems. I drew the recursive tree and each step had different value for mask and position.
Can't understand overlapping subproblems
hello @aman212yadav Bhaiya how is 001 and 101 same??
moreover in the video we have made a 2d dp and accessing the dp[mask][city]
Here is my tree:
As you can see no step has same value for mask and city
yes but city number is not same
dp array stores answers like dp[0111][1(B)] and dp[0111][2©]
also going from c->d and b->d will have different answer because of different weight
just to show u overlapping problem.
here if u see at the bottom nodes, cost of going to 1 from 4 is 8 right?
and we are computing it more than one in case of brute force right?
if u store that result in array then we dont have to compute it again.
have given simple example just to show u overlapping cases
Yes we are computing it more than once but the overlap is only in leaf nodes and that answer we can access in O(1) Time from adjacency matrix. that answer is already stored in the grid.
Thanks for the link its very big but I don’t think I still understand the overlapping subproblems. Like your tree it also says that only the leaf nodes overlap but why store its answer when the same thing is stored in adjacency matrix
thanks!
if you have any simpler explanation or any other pls do share
Also can you explain in terms of mask and city as explained in video. check the tree I drew
consider this->
1->2->3-> { 4, 5, 6 } ->1 … case 1
1->3->2-> {4, 5, 6 } -> 1 … case 2
here if u see subproblem
{4,5,6} -> 1 it is there in both the cases right?
now to compute the cost we will first solve this subproblem ( {4,5,6}->1 ) let say it return x (it will be same in both the case irrespective of what previous city is).
now here comes the role of previous city.
to determine the cost from previous city we need to add cost from previous city to one of the city ( {4,5,6} )
in case one it may be c1 , in case 2 it may be c2
so overall cost from previous city to 1 for case 1 is c1 + x
overall cost from previous city to 1 for case 2 is c2 + x.
so this problem has overlapping subproblem shown above,
it has optimal substructure and hence we can say it is dp problem.
In terms of mask and city->
{4,5,6} can be represented as {111000}
overall state for case 1 -> {111000,3}
overall state for case 2 -> {111000,2}
1 Like
ohkk right!
the above problem had less vertices making it difficult to realise it
thanks I got it now
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.