题目链接
思路
分析动态规划题目的时候只需要考虑最后一个阶段,因为所有的阶段转化都是相同的,考虑最后一个阶段容易发现规律
在数组的动态规划问题中,一般 dp[i]
都是表示以 nums
以前 i 个元素组成(即 nums[i - 1]
)的状态;dp[i][j]
分别表示以 nums1
前 i 个元素(即 nums1[i - 1]
)组成和以 nums2
前 j 个元素(即 nums2[j - 1]
)组成的状态,以此类推
字符串也是个数组,是字符数组
表示状态
状态表示就是靠猜,但是会有猜的套路,一般都是通过最终结果和数组数量来猜
这个题和【DP】LeetCode 198. 打家劫舍十分相似,唯一的区别就是在首尾房子的选择上,这时候可以分为三种情况讨论:
- 打劫第一间房
- 打劫最后一间房
- 首尾两间都不打劫
如下图所示
图片来自labuladong
实际上第三种情况肯定是小于等于前面两种情况的,因为它的可选择性最少,不可能得出最大值,所以只需要判断前面两种情况取最大值即可。
定义 \(dp[i][j]\) 表示在情况 i 的状况下,前 j 个房间能打劫到的最大值。
找状态转移方程
思考的方向是:大问题的最优解怎么由小问题的最优解得到
与198题相似
\[dp[i][j]=\max (dp[i][j-1], dp[i][j-2]+nums[j-1]) \]边界处理
这一部分是本题最需要注意的点,因为两个遍历的起始点不同,所以初值设置也要单独考虑
dp[0][1] = nums[0];
dp[1][2] = nums[1];
代码
dp
数组版
class Solution {
public int rob(int[] nums) {
int n = nums.length;
if(n == 1){
return nums[0];
}
// dp[0] 求 nums[0 : n - 2] 的最大值
// dp[1] 求 nums[1 ; n - 1] 的最大值
int[][] dp = new int[2][n + 1];
dp[0][1] = nums[0];
dp[1][2] = nums[1];
for(int i = 2; i < n; i++){
dp[0][i] = Math.max(dp[0][i - 1], dp[0][i - 2] + nums[i - 1]);
}
for(int i = 3; i <= n; i++){
dp[1][i] = Math.max(dp[1][i - 1], dp[1][i - 2] + nums[i - 1]);
}
return Math.max(dp[0][n - 1], dp[1][n]);
}
}
标签:nums,int,最大值,II,DP,数组,打家劫舍,LeetCode,dp
From: https://www.cnblogs.com/shixuanliu/p/17352875.html