动态规划

[Leetcode 198]
解法：一个经典的dp题，从选与不选的角度进行考虑，
终止条件是第0个的时候只有一个可以选，有两个的时候，选二者中大的那个。

参考：

代码：

[Leetcode 213]
解法：由于有环，那么给他拆分成[0,n-1] 和 [1,n]两个部分进行分别dp，最后取两个区间中取值大的。
代码：

[Leetcode 139]
解法(4种)

解法一: DFS

解法二: 记忆化DFS

解法三: bottom up DP
[子问题定义] : DP子问题是从0开始到当前位置的子串是否可分(dp[i] == true?)，当前位置总共有n个可能，所以子问题的个数是n个。
使用hashset转储dict
构建dp数组，默认初始空串是可分的即dp[0]=1,
遍历初始串，验证从前面可分的子串尾部到当前位置的字符串([j为dp[j]==1, i])是否在字典中，如果在字典中则记录当前位置可分

解法四: Bottom up DP + max trick

代码:

[Leetcode 124]
解法:
找二叉树中的最大路径和，首先要考虑清楚是从上往下找，还是从下往上找，通过观察树的结构， 我们发现从下到上最好找。

1、最优子结构 因为树是由一个个更小的结点树组成，所以我们可以把问题分解成一个个更小的树。 当树的结点只有一个时，最大的路径就是他自身，让树的高度为2时，根节点的最大路径为左右结点中的最大值加上根节点本身的值：max(l, r) + root.val， 如果左右结点都为负数，还没有自身的值大呢，所以我们取其中的最大值。maxSubSubTree = max(max(l, r) + root.val, root.val) 知道了二叉树的最优左右路径，我们需要比较整体路径，maxSubTree = max(maxSubSubTree, l+r+root.val)。 再将以该结点为根节点的二叉树的最大路径和，和全局的路径和比较，取两者最大值，res = max(res, maxSubTree)2、重叠子问题 从下往上走，当底层的最优路径找出来了， 上一层结点就能直接用下一层的结果,依次向上递推，求解过程都简化成了对若干个个高度为2 的二叉树的操作。当递归完成时，根节点的值就是整颗二叉树的最大路径和。

代码:

[Leetcode 128]
解法：(参考)
使用hashmap来构建，将数组中的值作为键，连续元素数目作为边界值，并存储在hashmap的连续区域边界节点中。
节点更新有三种情况:

当前元素在hashmap中没有左右邻居，那么该节点的hashmap值为1 ;
当前元素在hashmap中有左或右邻居(只存在一边)，那么该节点的hashmap值为其对应左右边界的连续值加1
当前元素能够桥接两个连续区域，那么该节点的hashmap值可以不关心，但是其左侧的左边界值与右侧部分的右边界值对应加一。

代码：