The question asked in the video was, find the smallest height of a node that can be visited from subtree of x?
And here’s the graph. What I can’t understand how dp[3] and dp[9] value not same. What I know that they both have same parent so their value gonna be dp[3]=1 and dp[9]=1 as well. That’s what I think.
you have to count the level you can reach by taking only 1 backedge.so for 3 we can go to 5 or 6 and then 1 making it 0 .but for 9 we can go to 11 and then 9 so 1
Okay. May be I didn’t get it very well. Can you tell me what dp[x] actually means where x is a node?
please share the timestamp from the video
Okay. So in this problem in top down approach, we need to take dp table where we can store the values so dp[] is an array in here where all the heights of a node stored. Like from the graph above, we can fill up the dp[] table like dp[0]=0, dp[3]=0, dp[9]=1 and so on.
So, my question is, what dp[x] is actually mean if x is a node?
dp[x]=the smallest height of a node that can be visited from subtree of x
What’s that even supposed to mean? Can you please try to explain it to me from that above graph? I actually didn’t understand the meaning of dp[x].
So that node is present in the subtree of x?
Which node we’re talking about in this definition?
The question is to find that for each note if we go into the subtree of that node what is the smallest height I can reach by travelling in that subtree. Dont overthink this. This is just a question to understand dp on graphs.
you’re saying same thing again and again, and not giving any example or justifiable answer of my questions.
Tell me, what’s dp[3] actually means in this above graph?
Dp[3] means what s the minimum level of a node u can reach from the subtree of 3. So hwre we have answer 0 coz in the subtree of 3 there exists 5 which can lead us to 1, the least possible node level
