比较简单的 DP。先写一个数组版:
impl Solution { pub fn rob(nums: Vec<i32>) -> i32 { // f(1) = nums[0] // f(2) = max(nums[0], nums[1]) // f(3) = max(f(1) + nums[2], f(2)) // f(4) = max(f(2) + nums[4], f(3)) // f(n) = max(f(n-2) + nums[n], f(n-1)) // // example1 // f(1) = 1 // f(2) = max(1, 2) = 2 // f(3) = max(1 + 3, 2) = 4 // f(4) = max(2 + 1, 4) = 4 // // example2 // f(1) = 2 // f(2) = 7 // f(3) = max(2 + 9, 2) = 11 // f(4) = max(3 + 7, 11) = 11 // f(5) = max(1 + 11, 11) = 12
if nums.len() == 1 { return nums[0]; }
let mut arr = vec![0; nums.len()]; arr[0] = nums[0]; arr[1] = nums[0].max(nums[1]);
for i in 2..nums.len() { let a = arr[i-2] + nums[i]; let b = arr[i-1]; arr[i] = a.max(b); }
arr[arr.len() - 1] }}
然后再优化一下:
impl Solution { pub fn rob(nums: Vec<i32>) -> i32 { // f(1) = nums[0] // f(2) = max(nums[0], nums[1]) // f(3) = max(f(1) + nums[2], f(2)) // f(4) = max(f(2) + nums[4], f(3)) // f(n) = max(f(n-2) + nums[n], f(n-1)) // // example1 // f(1) = 1 // f(2) = max(1, 2) = 2 // f(3) = max(1 + 3, 2) = 4 // f(4) = max(2 + 1, 4) = 4 // // example2 // f(1) = 2 // f(2) = 7 // f(3) = max(2 + 9, 2) = 11 // f(4) = max(3 + 7, 11) = 11 // f(5) = max(1 + 11, 11) = 12
if nums.len() == 1 { return nums[0]; }
let mut states = vec![ nums[0], nums[0].max(nums[1]), ]; let mut index = 0;
for i in 2..nums.len() { states[index] = if index == 0 { let a = states[0] + nums[i]; let b = states[1]; a.max(b) } else { let a = states[1] + nums[i]; let b = states[0]; a.max(b) };
index = if index == 0 { 1 } else { 0 }; }
states[if index == 0 { 1 } else { 0 }] }}