代码随想录打家劫舍+树形DP入门

动态规划part07

198.打家劫舍

视频讲解：https://www.bilibili.com/video/BV1Te411N7SX

https://programmercarl.com/0198.%E6%89%93%E5%AE%B6%E5%8A%AB%E8%88%8D.html  

1. dp数组：进入房屋i能够偷得得最大金额dp[i]
2. 递推公式：根据不相邻原则进入房间i能够偷到得总金额是由进入房间i-2或者房间i-3累计得到的，dp[i] = value[i] + max(dp[i-2], dp[i-3]);
3. 初始化dp[0],dp[1],dp[2]
4. 遍历房间

213.打家劫舍II

视频讲解：https://www.bilibili.com/video/BV1oM411B7xq

https://programmercarl.com/0213.%E6%89%93%E5%AE%B6%E5%8A%AB%E8%88%8DII.html

在抢第一个房间就不考虑最后一个，反之，抢最后一个房间就不考虑第一个房间

337.打家劫舍III

视频讲解：动态规划，房间连成树了，偷不偷呢？| LeetCode：337.打家劫舍3_哔哩哔哩_bilibili

代码随想录

树形DP入门

1. dp[i] = {dp[0], dp[1]}含义：下标0，1表示状态不偷当前节点和偷当前节点，数值表示在这两种状态下得到的最大金额
2. 递推偷当前根节点就不能偷左右儿子，不偷当前根偷不偷左右儿子都行取最大值
3. 后序遍历自树底向上遍历