Coins in a Line III
虽然是hard，但是真正理解起来并不难。关键是要知道区间dp的概念。因为棋手是前后端都可以选，单个状态dp不好表示，所以利用区间dp[i][j]表示在i->j这个区间先手能取到的最大值。
dp[i][j]=sum[i][j]-min(dp[i][j-1],dp[i+1][j])。这道题用记忆化搜索的递归方法来实现。
dp[i][j]=sum[i][j]-min(dp[i][j-1],dp[i+1][j])。这道题用记忆化搜索的递归方法来实现。
776. Split BST
Problem: Given a Binary Search Tree (BST) with root node root , and a target value V , split the tree into two subtrees where one subtree has nodes that are all smaller or equal to the target value, while the other subtree has all nodes that are greater than the target value. It's not necessarily the case that the tree contains a node with value V . Additionally, most of the structure of the original tree should remain. Formally, for any child C with parent P in the original tree, if they are both in the same subtree after the split, then node C should still have the parent P. You should output the root TreeNode of both subtrees after splitting, in any order. Example 1: Input: root = [4,2,6,1,3,5,7], V = 2 Output: [[2,1],[4,3,6,null,null,5,7]] Explanation: Note that root, output[0], and output[1] are TreeNode objects, not arrays. The given tree [4,2,6,1,3,5,7] is represented by the following diagram: 4 / \ 2 6 / \ / \ 1
评论
发表评论