思路大家如果刚接触这样的题目，会有点困惑，当前的状态我是偷还是不偷呢？仔细一想，当前房屋偷与不偷取决于前一个房屋和前两个房屋是否被偷了。所以这里就更感觉到，当前状态和前面状态会有一种依赖关系，那么这种依赖关系都是动规的递推公式。当然以上是大概思路，打家劫舍是dp解决的经典问题，接下来我们来动规五部曲分析如下：1确定dp数组（dptable）以及下标的含义dp[i]：考虑下标i（包括i）以内的房屋，最多可以偷窃的金额为dp[i]。2确定递推公式决定dp[i]的因素就是第i房间偷还是不偷。如果偷第i房间，那么dp[i]=dp[i-2]+nums[i]，即：第i-1房一定是不考虑的，找出下标i-2（
代码随想录训练营day48动态规划模块打家劫舍问题文章目录1.leetcode198.打家劫舍1.1思路1.2做题步骤及详细代码2.leetcode213.打家劫舍Ⅱ2.1思路2.2做题步骤及详细代码3.leetcode337.打家劫舍Ⅲ3.1思路3.2做题步骤及详细代码1.leetcode198.打家劫舍力扣题目链接1.1思路 这题对于我来说比较不好想的就是递推公式，假如现在准备考虑偷第i家，那么偷了i-1家的时候，就不能偷第i家了，所以此时dp[i]=dp[i-1];如果没有偷第i-1家，那么需要得到最大金额的话，i-2家肯定被偷了，此时dp[i-2]+nums[i]。1.2做题步骤及详
代码随想录训练营day48动态规划模块打家劫舍问题文章目录1.leetcode198.打家劫舍1.1思路1.2做题步骤及详细代码2.leetcode213.打家劫舍Ⅱ2.1思路2.2做题步骤及详细代码3.leetcode337.打家劫舍Ⅲ3.1思路3.2做题步骤及详细代码1.leetcode198.打家劫舍力扣题目链接1.1思路 这题对于我来说比较不好想的就是递推公式，假如现在准备考虑偷第i家，那么偷了i-1家的时候，就不能偷第i家了，所以此时dp[i]=dp[i-1];如果没有偷第i-1家，那么需要得到最大金额的话，i-2家肯定被偷了，此时dp[i-2]+nums[i]。1.2做题步骤及详
目录打家劫舍Ⅰ题目分析 代码一 代码二打家劫舍Ⅱ 打家劫舍Ⅰ你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。 输入：[2,7,9,3,1]输出：12解释：偷窃1号房屋(金额=2),偷窃3号房屋(金额=9)，接着偷窃5号房屋(金额=1)。 偷窃到的最高金额=2+9+1=12。题目分析 nums27931R27+09+23+71+11NR0271111 R
目录打家劫舍Ⅰ题目分析 代码一 代码二打家劫舍Ⅱ 打家劫舍Ⅰ你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。 输入：[2,7,9,3,1]输出：12解释：偷窃1号房屋(金额=2),偷窃3号房屋(金额=9)，接着偷窃5号房屋(金额=1)。 偷窃到的最高金额=2+9+1=12。题目分析 nums27931R27+09+23+71+11NR0271111 R
一、题目大意标签:动态规划https://leetcode.cn/problems/house-robber你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。示例1：输入：[1,2,3,1]输出：4解释：偷窃1号房屋(金额=1)，然后偷窃3号房屋(金额=3)。 偷窃到的最高金额=1+3=4。示例2：输入：[2,7,9,3,1]输出：12解释：偷窃1号房屋(金额
一、题目大意标签:动态规划https://leetcode.cn/problems/house-robber你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。示例1：输入：[1,2,3,1]输出：4解释：偷窃1号房屋(金额=1)，然后偷窃3号房屋(金额=3)。 偷窃到的最高金额=1+3=4。示例2：输入：[2,7,9,3,1]输出：12解释：偷窃1号房屋(金额
题目连接：337.打家劫舍III-力扣（LeetCode） 题目分析： 二叉树的后续遍历，dp[root]表示root节点的最大收益 dp[root]=max(dp[root.left]+dp[root.right], root.val+dp[root.left.left]+dp[root.left.right]+dp[root.right.left]+dp[root.right.right])我们可以在原始的二叉树上进行记录，因为题目中没有说不允许改变二叉树的内容；我们使用二叉树的后续遍历，当前节点的最大收益为取当前节点，和不取当前节点的最大值，不取当前节点的话那就是两个子数的根节
题目连接：337.打家劫舍III-力扣（LeetCode） 题目分析： 二叉树的后续遍历，dp[root]表示root节点的最大收益 dp[root]=max(dp[root.left]+dp[root.right], root.val+dp[root.left.left]+dp[root.left.right]+dp[root.right.left]+dp[root.right.right])我们可以在原始的二叉树上进行记录，因为题目中没有说不允许改变二叉树的内容；我们使用二叉树的后续遍历，当前节点的最大收益为取当前节点，和不取当前节点的最大值，不取当前节点的话那就是两个子数的根节
