【算法训练 day50 打家劫舍、打家劫舍Ⅱ、打家劫舍Ⅲ】

---

一、打家劫舍-LeetCode 198

Leecode链接: leetcode 198

思路

dp数组含义为：当前数组范围下能偷到的最多的钱。递推公式为:dp[j] = max(dp[j-2]+nums[j],dp[j-1])，初始化dp[0] = nums[0]，初始化dp[1] = nums[1]。

---

二、打家劫舍Ⅱ-LeetCode 213

Leecode链接: LeetCode 213

思路

与上一题类似，但需要针对不同情况进行区分，可将数组分为不带首位元素带末尾元素的、带首位元素不带末尾元素，然后将这两种情况的值都求出来进行对比大小并取最大值。其余则与上一题完全一致。

---

三.打家劫舍Ⅲ-LeeCode 337

Leecode链接: LeetCode 337

思路

这道题有点不一样，但基本思路一致。不一样在于每次取得值不能是父子节点了，所以需要使用后序遍历，这样就能保证只用考虑本层递归的节点是否需要取。dp数组只用存储两个元素，即该层元素取得话最大值是多少，不取的话最大值是多少。并将该结果返回上一层递归，然后上一层递归再记录不同情况的值。