文章目录

系列文章目录

一、 数组类型解题方法一：二分法

二、数组类型解题方法二：双指针法

三、数组类型解题方法三：滑动窗口

四、数组类型解题方法四：模拟

五、链表篇之链表的基础操作和经典题目

六、哈希表篇之经典题目

七、字符串篇之经典题目

八、字符串篇之 KMP

九、解题方法：双指针

十、栈与队列篇之经典题目

十 一、栈与队列篇之 top-K 问题

十 二、二叉树篇之二叉树的前中后序遍历

十 三、二叉树篇之二叉树的层序遍历及相关题目

十 四、二叉树篇之二叉树的属性相关题目

十 五、 二叉树篇之二叉树的修改与构造

十 六、 二叉树篇之二叉搜索树的属性

十 七、二叉树篇之公共祖先问题

十 八、二叉树篇之二叉搜索树的修改与构造

十 九、回溯算法篇之组合问题

二 十、回溯算法篇之分割、子集、全排列问题

二十一、贪心算法篇之入门题目

二十二、贪心算法篇之进阶题目

二十三、动态规划篇之基础题目

二十四、动态规划篇之背包问题：01背包

二十五、动态规划篇之背包问题：完全背包

更新中 ……

前言

刷题路线来自 ：代码随想录

题录

198. 打家劫舍

Leetcode 链接

题解：

dp[i]: 偷到 i 房间盗窃的最大金额

递推公式：dp[i] = max(不偷 i 房间，偷 i 房间) = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);

class Solution {public int rob(int[] nums) {int len = nums.length;int[] dp = new int[len + 1];dp[1] = nums[0];for (int i = 2; i <= len; i++) {dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);}return dp[len];}}

213. 打家劫舍 II

Leetcode 链接

题解：

不同于上题的是最后一个房间与第一个房间相连，也就是者两个房间只能偷一个，我们可以分两个区间偷

class Solution {public int rob(int[] nums) {int len = nums.length;if (len == 1) return nums[0];return Math.max(robRange(Arrays.copyOfRange(nums, 0, len - 1)), robRange(Arrays.copyOfRange(nums, 1, len)));}public int robRange(int[] nums) {int len = nums.length;int[] dp = new int[len + 1];dp[1] = nums[0];for (int i = 2; i <= len; i++) {dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);}return dp[len];}}

如果觉得《Leetcode 刷题笔记(二十六) ——动态规划篇之经典问题：打家劫舍》对你有帮助，请点赞、收藏，并留下你的观点哦！