資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 實現打家劫舍 II
假設你是一名職業劫匪，你計劃沿街搶劫房屋。每棟房子都儲存著一定數量的錢。所有房屋都排成一個圓圈。這意味著第一棟房子是最後一棟房子的鄰居。我們必須記住，相鄰的房屋連線著安全系統，如果在同一個晚上闖入兩棟相鄰的房屋，它會自動報警。因此，如果我們有一個整數列表，表示每棟房子的金額，請確定你可以在一個晚上搶劫的最大金額，而不會觸發警報。例如，如果陣列是 [1,2,3,1]，則輸出將是 4。
為了解決這個問題，我們將遵循以下步驟：
- 我們使用一個名為 solve() 的模組，它將接收陣列、起始位置和結束位置作為引數，其作用如下：
- ans := nums[start]
- 建立一個用於動態規劃的表格，命名為 dp，大小與 nums 相同。
- dp[start] := nums[start]
- for i := start + 1 to end
- last := dp[i – 1]
- lastToLast := 如果 i – 2 存在，則為 dp[i – 2]，否則為 0
- dp[i] := nums[i] + lastToLast 和 last 的最大值
- ans := dp[i] 和 ans 的最大值
- return ans
- 搶劫過程如下：
- n := nums 的大小
- 如果 n 為零，則返回 0
- 如果 n = 1，則返回 nums[0]
- 返回 solve(nums, 0, n - 2) 和 solve(nums, 1, n – 1) 的最大值
讓我們看看下面的實現，以便更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int solve(vector <int>& nums, int start, int end){
int ans = nums[start];
vector <int> dp(nums.size());
dp[start] = nums[start];
for(int i = start + 1; i <= end; i++){
int last = dp[i - 1];
int lastToLast = i - 2 < start? 0 : dp[i - 2];
dp[i] = max(nums[i] + lastToLast, last);
ans = max(dp[i], ans);
}
return ans;
}
int rob(vector<int>& nums) {
int n = nums.size();
if(!n)return 0;
if(n == 1)return nums[0];
return max(solve(nums, 0, n - 2), solve(nums, 1, n - 1));
}
};
main(){
vector<int> v = {1,2,3,5};
Solution ob;
cout << ob.rob(v);
}輸入
[1,2,3,5]
輸出
7
更新於: 2020年5月4日
712 次瀏覽
廣告