SOURCE

// 1. 一条线，两点不能相邻

// function robHouse(start, houses) {
//     console.log(start, houses.length)
//     if (start >= houses.length) return 0
//     robValue = Math.max(robHouse(start + 1, houses), robHouse(start + 2, houses) + houses[start])
//     return robValue;
// }

// let rob = robHouse(0, [1,2,2])
// console.log(rob)




// function dp(start, houses, memo) {
//     if(memo[start]) return memo[start]
//     if(start >= houses.length) return 0
//     let rob = Math.max(dp(start+1,houses,memo), houses[start] + dp(start+2,houses,memo))
//     memo[start] = rob
//     return rob
// }

// function robHouse(start, houses) {
//     let memo = new Array(houses.length + 2);
//     for(let i = 0; i < houses.length + 2; i ++) {
//         memo[i] = 0;
//     }
//     return dp(start, houses, memo)
// }

// let rob = robHouse(0, [1,2,2,3,5])
// console.log(rob)




// function robHouse(start, houses) {
//     let rob = 0, rob_i_1 = 0, rob_i_2 = 0
//     for(let i = houses.length -1; i >= 0; i --) {
//         rob = Math.max(rob_i_1, houses[i] + rob_i_2)
//         rob_i_2 = rob_i_1
//         rob_i_1 = rob
//     }
//     return rob
// }

// let rob = robHouse(0, [1,2,2,3,5])
// console.log(rob)




// 2. 一条环，首尾相连，两点不能相邻

// function robHouse(houses) {
//     let rob = 0, rob_i_1 = 0, rob_i_2 = 0
//     for(let i = houses.length -1; i >= 0; i --) {
//         rob = Math.max(rob_i_1, houses[i] + rob_i_2)
//         rob_i_2 = rob_i_1
//         rob_i_1 = rob
//     }
//     return rob
// }

// function robHouseAsCircle(circleHouses) {
//     let headHouses = [], tailHouses = []
//     for(let i = 0; i < circleHouses.length; i ++) {
//         if(i != 0 ) tailHouses.push(circleHouses[i])
//         if(i < circleHouses.length - 1) headHouses.push(circleHouses[i])
//     }
//     console.log(headHouses)
//     console.log(tailHouses)
//     return Math.max(robHouse(headHouses), robHouse(tailHouses))
// }

// let rob = robHouseAsCircle([1,2,2,3,5])
// console.log(rob)





// 3. 打劫二叉树，两点不能相邻

// function robTree(start, houses) {
//     if(start >= (houses.length)) return 0
//     let robRoot = houses[start] 
//                 + robTree(2*(2*start+1)+1, houses) + robTree(2*(2*start+1)+2, houses) 
//                 + robTree(2*(2*start+2)+1, houses) + robTree(2*(2*start+2)+2, houses)
//     let robChildren = robTree((2*start+1)+1, houses) + robTree((2*start+2)+1, houses)
//     return Math.max(robRoot, robChildren)
// }


// let rob = robTree(0, [1,2,2,3,5])
// console.log(rob)


// 规划备忘录
// function robHouseAsTree(houses) {
//     let memo = new Array(houses.length)
//     for (let i = 0; i < houses.length; i ++) {
//         memo[i] = -1
//     }
//     return robTree(0, houses, memo)
// }

// function robTree(start, houses, memo) {
//     if(start >= (houses.length) || houses[start] == null) return 0
//     console.log(memo[start])
//     if(memo[start] == -1) {
//         let robRoot = houses[start] 
//                 + robTree(2*(2*start+1)+1, houses, memo) + robTree(2*(2*start+1)+2, houses, memo) 
//                 + robTree(2*(2*start+2)+1, houses, memo) + robTree(2*(2*start+2)+2, houses, memo)
//         let robChildren = robTree((2*start+1)+1, houses, memo) + robTree((2*start+2)+1, houses, memo)
//         memo[start] = Math.max(robRoot, robChildren)
//         console.log(memo[start])
//     }
//     return memo[start]
// }


// let rob = robHouseAsTree([1,2,2, null, 3,5, null])
// console.log(rob)



function robHouseAsTree(houses) {
    let robArray = robTree(0, houses)
    return Math.max(robArray[0], robArray[1])
}

// 返回数组，0 打劫根节点 1 打劫孩子节点
function robTree(start, houses) {
    if(start >= (houses.length) || houses[start] == null) return [0,0]

    let robLC = robTree(2*start+1, houses)
    let robRC = robTree(2*start+2, houses)
    let robRoot = houses[start] + robLC[1] + robRC[1]
    let robChildren = robLC[0] +robRC[0]

    return [robRoot, robChildren]
}


let rob = robHouseAsTree([1,2,2, null, 3,5, null])
console.log(rob)