198.打家劫舍
198. 打家劫舍 - 力扣(LeetCode)
思路:最简单的动态规划思路。递推公式是dp[j] = Math.max(dp[j - 1], dp[j - 2] + nums[j]),要么打劫第j个房子(下一个打劫的房子不能和j相邻),要么不打劫第j个房子。
注意:背包问题只是动态规划的一种题型,请记得动态规划的思路初衷。
213.打家劫舍II
213. 打家劫舍 II - 力扣(LeetCode)
思路:让数组没有成环的情况:掐头包括尾,掐尾包括头。动态规划计算结果取最大值。
337.打家劫舍III
337. 打家劫舍 III - 力扣(LeetCode)
思路:递推加动态规划。递归到左和右节点,取得该节点偷还是不偷的最大值。要用后序遍历。