这题看了好多年一直没点进来做,以为是个什么水题。。。没想到一点都不水。。。
视频主总结的特别好: 一般问return boolean, number 这种不用return具体的,很多都可以DP。
参考:https://www.youtube.com/watch?v=HWJEMKWzy-Q
知道是DP以后还是感觉很难。毕竟和以往练习的matrix, string 的DP很不一样。竟然要从BST里来找关系。 这个。。。
我做了一遍发现,这道题最难的部分就是如何处理transfer function. 很容易value被迷惑。 其实我们应该管的是nodes的数量还不是数值。比如左下角有2个node的话有几种组合。
还有一个tricky的就是视频里transfer func: n-j-1这个,实际上应该是i-j-1.