1, Title [LeetCode-198]
You are a professional thief who plans to steal houses along the street. There is a certain amount of cash hidden in each room. The only restrictive factor affecting your theft is that the adjacent houses are equipped with interconnected anti-theft systems. If two adjacent houses are intruded by thieves on the same night, the system will automatically alarm.
Given a non negative integer array representing the amount stored in each house, calculate the maximum amount you can steal overnight without touching the alarm device.
Example 1:
Input: [1,2,3,1]
Output: 4
Explanation: steal house 1 (amount = 1) and then steal house 3 (amount = 3).
Maximum amount stolen = 1 + 3 = 4.
Example 2:
Input: [2,7,9,3,1]
Output: 12
Explanation: steal house 1 (amount = 2), steal house 3 (amount = 9), and then steal house 5 (amount = 1).
Maximum amount stolen = 2 + 9 + 1 = 12.
Tips:
- 1 <= nums.length <= 100
- 0 <= nums[i] <= 400
2, Train of thought
dynamic programming
From the meaning of the question, that is to find the maximum sum of elements in the array nums (the elements taken out cannot be adjacent), which is just the opposite of day36 maximum sub order sum. This question requires the maximum continuous sum of elements in the array. Let dp[i][0] indicate that you choose not to steal money from house I (I is calculated from 0), that is, you choose not to add this element after traversing the ith element of the array; dp[i][1] indicates that after traversing the ith element of the array, select to add the element.
For dp[i][0], either the i-1 company didn't steal (i.e. dp[i-1][0]) or the i-1 company stole (i.e. dp[i-1][1]), directly take the largest of the two; For dp[i][1], you can only steal house I after house i-1 is not stolen.
Therefore, the dynamic programming transfer equation is obtained:
dp[i][0] = max(dp[i-1][0], dp[i-1][1])
dp[i][1] = dp[i-1][0] + nums[i]
Initial condition: dp[0][0] = 0, dp[0][1] = nums[0]
class Solution {
public:
int rob(vector<int>& nums) {
int n = nums.size();
vector<vector<int>> dp(n);
for(int i = 0; i < n; i++)
dp[i] = vector<int>(2);//Declare dynamic programming array
dp[0][0] = 0;
dp[0][1] = nums[0];//Initial conditions for initializing dynamic programming array
for(int i = 1; i < n; i++)
{
dp[i][0] = max(dp[i-1][0], dp[i-1][1]);
dp[i][1] = dp[i-1][0] + nums[i];
}
return max(dp[n-1][0], dp[n-1][1]);
}
};
Dynamic programming optimization (rolling array)
Similarly, it can be greatly optimized. Instead of using the implementation of array, it can only use two variables dp0 and dp1 for n-1 iterations.
class Solution {
public:
int rob(vector<int>& nums) {
int n = nums.size();
int dp0 = 0;
int dp1 = nums[0];//Initial conditions of dynamic programming
for(int i = 1; i < n; i++)
{
int newDp0 = max(dp0, dp1);
dp1 = dp0 + nums[i];
dp0 = newDp0;
}
return max(dp0, dp1);
}
};
3, Official solution (source: LeetCode)
Method: dynamic programming (another dynamic programming idea)
Consider the simplest case first. If there is only one house, you can steal the house to the maximum total amount. If there are only two houses, because the two houses are adjacent, you can't steal at the same time, and you can only steal one of them. Therefore, if you choose the house with higher amount to steal, you can steal to the maximum total amount.
If the number of houses is more than two, how to calculate the maximum total amount that can be stolen? For house K (k > 2), there are two options:
- If you steal house K, you cannot steal house K − 1. The total amount of theft is the sum of the maximum total amount of the first k − 2 houses and the amount of house K.
- Do not steal the k-th house, and the total amount of theft is the maximum total amount of the first k − 1 house.
Select the option with a larger total amount of theft from the two options. The total amount of theft corresponding to this option is the maximum total amount that can be stolen from the first k houses.
Use dp[i] to represent the maximum total amount that can be stolen from the first I houses, then there is the following state transition equation:
dp[i] = max(dp[i-2]+nums[i], dp[i-1])
The boundary conditions are: dp[0] = nums[0], dp[1] = max(nums[0], nums[1])
The final answer is dp[n-1], and N is the length of the array
class Solution {
public:
int rob(vector<int>& nums) {
if (nums.empty()) {
return 0;
}
int size = nums.size();
if (size == 1) {
return nums[0];
}
vector<int> dp = vector<int>(size, 0);
dp[0] = nums[0];
dp[1] = max(nums[0], nums[1]);
for (int i = 2; i < size; i++) {
dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
}
return dp[size - 1];
}
};
Author: LeetCode-Solution
Link: https://leetcode-cn.com/problems/house-robber/solution/da-jia-jie-she-by-leetcode-solution/
Source: force buckle( LeetCode)
The copyright belongs to the author. For commercial reprint, please contact the author for authorization. For non-commercial reprint, please indicate the source.The above method uses an array to store the results. Considering that the maximum total amount of each house is only related to the maximum total amount of the first two houses of the house, a rolling array can be used to store only the maximum total amount of the first two houses at each time.
class Solution {
public:
int rob(vector<int>& nums) {
if (nums.empty()) {
return 0;
}
int size = nums.size();
if (size == 1) {
return nums[0];
}
int first = nums[0], second = max(nums[0], nums[1]);
for (int i = 2; i < size; i++) {
int temp = second;
second = max(first + nums[i], second);
first = temp;
}
return second;
}
};
Author: LeetCode-Solution
Link: https://leetcode-cn.com/problems/house-robber/solution/da-jia-jie-she-by-leetcode-solution/
Source: buckle force( LeetCode)
The copyright belongs to the author. For commercial reprint, please contact the author for authorization. For non-commercial reprint, please indicate the source.Complexity analysis
- Time complexity: O(n), where n is the length of the array. You only need to traverse the array once.
- Space complexity: O(1). Using the rolling array, you can only store the maximum total amount of the first two houses without storing the results of the whole array, so the space complexity is O(1).
4, Learning experience
① For this problem, there are two ideas for dynamic programming state transition equation:
(1) dp[i][0] means that you choose not to steal the money of house I (I is calculated from 0),; dp[i][1] means that you choose not to steal money from the i-th house.
dp[i][0] = max(dp[i-1][0], dp[i-1][1])
dp[i][1] = dp[i-1][0] + nums[i]
(2) dp[i] refers to the maximum total amount that can be stolen from the first I houses
dp[i] = max(dp[i-2]+nums[i], dp[i-1])
② When the problem of array data structure involves many situations and there is a recursive relationship, dynamic programming can be considered first
③ The dynamic programming optimization scheme of rolling array can optimize the spatial complexity from O(n) to O(1)