LeetCode.213.打家劫舍2
難度：medium
這道題是LeetCode.198. 打家劫舍 的升級版；
因為成了環的緣故要分類討論取最大值：
-
包括首元素不包括尾元素的區間
-
不包括首元素包括尾元素的區間
Java：
動態規劃：
class Solution {
public int rob(int[] nums) {
int length = nums.length;
//特殊情況處理
if (length == 0) {
return 0;
}
if (length == 1) {
return nums[0];
}
if (length == 2) {
return Math.max(nums[0], nums[1]);
}
//兩種情況討論，包括首元素不包括尾元素的區間和不包括首元素包括尾元素的區間
int case1 = robmoney(nums, 0, length - 2);
int case2 = robmoney(nums, 1, length - 1);
return Math.max(case1, case2);
}
public int robmoney(int[] nums, int start, int end) {
int len = end - start + 1;
//dp[i]前i號房能夠偷竊到的最高金額
int[] dp = new int[len + 1];
//初始化
dp[start] = nums[start];
dp[start + 1] = Math.max(nums[start], nums[start + 1]);
// 遞推方程：dp[i] = Math.max(dp[i - 1], dp[i - 2] +nums[i])
for (int i = start + 2; i <= end; i++) {
dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
}
return dp[end];
// //這個也可以通過
// //初始化
// dp[0] = nums[start];
// dp[1] = Math.max(nums[start], nums[start + 1]);
// // 遞推方程：dp[i] = Math.max(dp[i - 1], dp[i - 2] +nums[i])
// for (int i = 2; i <= end - start; i++) {
// dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[start + i]);
// }
// return dp[end - start];
}
}復雜度分析：
- 時間復雜度：O(n)
- 空間復雜度：O(n)
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/395434.html
標籤：其他