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

本文主要是介绍【算法训练 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数组只用存储两个元素，即该层元素取得话最大值是多少，不取的话最大值是多少。并将该结果返回上一层递归，然后上一层递归再记录不同情况的值。

这篇关于【算法训练 day50 打家劫舍、打家劫舍Ⅱ、打家劫舍Ⅲ】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---