Struggling when solving tree DP problems. Would love some advice/tips(2021)

Question

So I started leetcode last month and even though I struggled during the first week, later I was able to understand how to solve them and now I can breeze through all the easy problems

Well not all actually, I get stuck whenever I see a problem related to trees or DP and the part which frustrates me is I don’t know why

I have practiced and understood recursion as well as memoization but still I’m not able solve these problems. Whenever I check the solution after struggling to come up with an answer, I realise how simple it actually is and I feel really stupid

Would really appreciate some advice !

Answer 1

For Tree dp , I used the same trick every-time .

Never do that recursion/backtracking stuff for tree dp , its just not very intuitive .

Make node "1" as the root of the tree .

Always, do the reverse bfs technique on tree and solve tree dp problems iteratively . Iterative things are usually very intuitive and the best for the mind to grasp . Traverse nodes at last level , then nodes at level : last - 1 , till you reach the root .

dp[i] should always store the best answer of node 'i' , which means if tree started from node 'i' and only the nodes below it (children , grandchildren existed) , then what would be the answer for our tree ? It would be dp[i] . After computing dp[i] for each node, dp[1] is the final answer :)

dp[i] is , in most cases a function of its children , and as we travelled from bottom , dp values for children of any node have already been calculated!

dp[i] = f(dp[child1],dp[child2],.....) , where child1,child2,child3,....childn are the direct children on node 'i' . (Tree is rooted at node '1')

Hope it helps!