1 dp * 2 times equals to this question: the final result will only be one of the two following situations: - first is not selected, then freely select in the following - last is not selected, then freely select in the following
(mut nums: Vec<i32>)
| 11 | /// - first is not selected, then freely select in the following |
| 12 | /// - last is not selected, then freely select in the following |
| 13 | pub fn rob(mut nums: Vec<i32>) -> i32 { |
| 14 | if nums.len() < 1 { return 0 } |
| 15 | if nums.len() == 1 { return nums[0] } |
| 16 | if nums.len() == 2 { return std::cmp::max(nums[0], nums[1]) } |
| 17 | let mut dp = vec![0; nums.len()]; |
| 18 | let last = nums.pop().unwrap(); |
| 19 | dp[0] = nums[0]; |
| 20 | dp[1] = std::cmp::max(nums[0], nums[1]); |
| 21 | for i in 2..nums.len() { |
| 22 | dp[i] = std::cmp::max(dp[i-1], dp[i-2] + nums[i]); |
| 23 | } |
| 24 | let res = dp[nums.len() - 1]; |
| 25 | nums.push(last); |
| 26 | nums.remove(0); |
| 27 | dp[0] = nums[0]; |
| 28 | dp[1] = std::cmp::max(nums[0], nums[1]); |
| 29 | for i in 2..nums.len() { |
| 30 | dp[i] = std::cmp::max(dp[i-1], dp[i-2] + nums[i]); |
| 31 | } |
| 32 | std::cmp::max(res, dp[nums.len() - 1]) |
| 33 | } |
| 34 | } |
| 35 | |
| 36 | #[cfg(test)] |