题本身不难，Easy 难度。
先从 Top-Down 的角度来想，如果我们定义 maxProfit(n) 为长度为 n 的 array 中所能得到的最大利益的话，不难看出在计算 maxProfit(n) 的时候，它的值只和前两个 subproblem 相关，即 maxProfit(n - 1) 和 maxProfit(n - 2).
由此我们发现了 DP 的第一个性质： overlap subproblems.
同时如果 maxProfit(n - 1) 和 maxProfit(n - 2) 都是其对应子问题的最优解的话，我们可以只利用这两个子问题的 solution，加上对当前元素的判断，构造出 maxProfit(n) 的最优解。
因此我们满足了 DP 的正确性性质: optimal substructure.
此题的另外考点在于空间的优化。因为每一个 size = n 的问题只和前面的 2 个子问题相关，我们显然不需要存储所有的状态，而可以用滚动数组优化空间占用。 滚动数组的简单用法就是“膜” （=。=），即对 dp[] 的 index 取 mod，
除数等于需要保存的状态数。
题外话，cicular buffer 很适合用于实现 fixed-size queue，一个 java 实现看一看
这个帖子
Copy public class Solution {
public int rob ( int [] nums) {
if (nums == null || nums . length == 0 ) return 0 ;
if ( nums . length == 1 ) return nums[ 0 ];
if ( nums . length == 2 ) return Math . max (nums[ 0 ] , nums[ 1 ]);
int [] dp = new int [ 2 ];
dp[ 0 ] = nums[ 0 ];
dp[ 1 ] = Math . max (nums[ 0 ] , nums[ 1 ]);
for ( int i = 2 ; i < nums . length ; i ++ ){
dp[i % 2 ] = Math . max (dp[(i - 2 ) % 2 ] + nums[i] , dp[(i - 1 ) % 2 ]);
}
return dp[( nums . length - 1 ) % 2 ];
}
} 这题考察环形数组中，subproblem 的拆分与覆盖。
数组变成环形之后，就需要考虑首尾相接的问题了~ 理论上说，对于长度为 n 的环形数组，我们现在有了 n 种不同的切分方式，去处理长度为 n 的线性数组。
不过我们不需要考虑所有的可能切分，因为只有相邻元素之间会出现问题。我们的 subproblem 不能再以 size = n 开始 top-down了，因为无法保证正确性； 但是 size = n - 1 的所有 subproblems，一定是正确的。我们只需要考虑，如何拆分 size = n - 1 的 subproblems，并且如何用他们构造出全局最优解。
只需要把环形数组拆分成两个头尾不同的 size = n - 1 的 subproblems 就可以了：
【1, 7, 5, 9, 2】
下面的 subproblem 覆盖了所有不抢最后一座房子的 subproblems；
【(1, 7, 5, 9) 2】
如下的 subproblem 覆盖了所有不抢第一座房子的 subproblems；
【1,(7, 5, 9, 2)】
如果最后的最优解第一座和最后一座房子都不抢，也一定会被包含在左右两个 subproblem 的范围内，因为其 size = n - 2;
【1, (7, 5, 9), 2】
由于我们不能同时抢第第一和最后一座房子，上面两个 overlap subproblem 一定覆盖了所有子问题的最优解，并且符合全局最优解的 optimal substructure，保证了算法的正确性。
易错点： 后半段数组的 index offset，合理的处置是用完全一样的 for loop，只在实际取元素的时候做 nums[i + 1]，不然计算后半段以 i = 3 开始时，覆盖的 dp[] 位置是错的。
Copy public class Solution {
public int rob ( int [] nums) {
if (nums == null || nums . length == 0 ) return 0 ;
if ( nums . length == 1 ) return nums[ 0 ];
if ( nums . length == 2 ) return Math . max (nums[ 0 ] , nums[ 1 ]);
int leftMax = helper(nums , 0 ) ;
int rightMax = helper(nums , 1 ) ;
return Math . max (leftMax , rightMax);
}
private int helper ( int [] nums , int start){
int max = 0 ;
int [] dp = new int [ 2 ];
dp[ 0 ] = nums[start];
dp[ 1 ] = Math . max (nums[start] , nums[start + 1 ]);
for ( int i = 2 ; i < nums . length - 1 ; i ++ ){
dp[i % 2 ] = Math . max (dp[(i - 1 ) % 2 ] , dp[(i - 2 ) % 2 ] + nums[i + start]);
}
return dp[( nums . length - 2 ) % 2 ];
}
} 回顾下这章一开始对动态规划的总结，可以很容易看出来，这题的左右子树 subproblem 是 disjoint.
因此这道题只有 optimal substructure，而没有 overlap subproblems.
先贴一段错误的代码 ，思路就是用 level order 遍历整棵树，存下 curSum ，然后用 House Robber 一样的思路去做 DP. 错误的原因在于，不应该直接舍弃掉一层，因为层与层之间并不是 fully connected，比如[2,1,3,null,4]，最优解是相邻两层上不相连的两个 node.
Copy public class Solution {
public int rob ( TreeNode root) {
if (root == null ) return 0 ;
List < Integer > lvlSum = new ArrayList < Integer >();
Queue < TreeNode > queue = new LinkedList < TreeNode >();
if (root != null ) queue . offer (root);
while ( ! queue . isEmpty ()){
int size = queue . size ();
int curSum = 0 ;
for ( int i = 0 ; i < size; i ++ ){
TreeNode node = queue . poll ();
curSum += node . val ;
if ( node . left != null ) queue . offer ( node . left );
if ( node . right != null ) queue . offer ( node . right );
}
lvlSum . add (curSum);
}
if ( lvlSum . size () == 1 ) return lvlSum . get ( 0 );
if ( lvlSum . size () == 2 ) return Math . max ( lvlSum . get ( 0 ) , lvlSum . get ( 1 ));
int [] dp = new int [ 2 ];
dp[ 0 ] = lvlSum . get ( 0 );
dp[ 1 ] = Math . max ( lvlSum . get ( 0 ) , lvlSum . get ( 1 ));
for ( int i = 2 ; i < lvlSum . size (); i ++ ){
dp[i % 2 ] = Math . max (dp[(i - 1 ) % 2 ] , dp[(i - 2 ) % 2 ] + lvlSum . get (i));
}
return dp[( lvlSum . size () - 1 ) % 2 ];
}
} 这道题只有 DP 的一个性质： optimal substructure，即用 subproblem (subtree) 的最优解可以构造出全局最优解。optimal substructure性质在 Tree 类问题中非常常见，因此遇到一个问题的时候，要注意按照其性质属性仔细辨别正确解法。
在 Tree 上做递归的时候返回顺序已然是 bottom-up，相对于每一个节点，并没有重复计算，也没有 overlap subproblems，因此这只是一个正常的递归搜索问题，而不需要依赖 DP 进行优化。
dfs 时间复杂度已经是 O(n) , n = # of nodes
Copy public class Solution {
public int rob ( TreeNode root) {
if (root == null ) return 0 ;
if ( root . left == null && root . right == null ) return root . val ;
int leftLvl = 0 , rightLvl = 0 ;
int subleftLvl = 0 , subrightLvl = 0 ;
if ( root . left != null ){
leftLvl = rob( root . left ) ;
subleftLvl = rob( root . left . left ) + rob( root . left . right ) ;
}
if ( root . right != null ){
rightLvl = rob( root . right ) ;
subrightLvl = rob( root . right . left ) + rob( root . right . right ) ;
}
return Math . max (subleftLvl + subrightLvl + root . val , leftLvl + rightLvl);
}
} 