I’m still doing this problem from the Range DP module, and I’m not sure what the supposed definition of the DP array is supposed to be.
I know that the target complexity is \mathcal{O}(n^3), but any 2D definition I come up with gets stuck on being unable to transition.
Right now, the most promising I’ve been able to come up with is this:
dp[a][b] = max diameter given that we start at a and end at b (inclusive)
but no information about the tree is preserved in this relation. Should one of the dimensions be a node ID, or am I missing something else?