Easy to solve. Just don’t forget the corner case.

Ideas: This problem has two solutions. Both solutions use dynamic programming. The first solution maintains three status for each stock so that it runs faster with the time complexity O(n). The second solution uses classical dynamic programming equation which runs slower with the time complexity O(n^2).

Solutions: Always remember the equation for dynamic programming: c[ i, j ] = max( c[ i , j-1 ], c[ i-1, j ] ). In this problem, houses locate in a binary tree. We can use recursive calls and dynamic programming ideas to solve it. By returning two values, res[0] contains subnodes’ value without child node’s value, res[1] contains subnodes’ value with child node’s value. Each node would create its own res and return it to its parent and finally, the root node choose the larger one as the answer.

Solutions: This problem(link) generates from the House Robber. Houses in this problem are not at a straight line but a cycle which means you can not rob both the first and the last house at the same time. To solve this trap we can divide the problem into two subproblems. 1. Compute the optimal value for house[0 : n-1]. 2. Compute the optimal value for house[1 : n]. The maximum value of these two is the final answer for this problem.

This is my first blog. Fighting 2020!