Leetcode 第198题. 打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例 1：

输入：[1,2,3,1] 输出：4 解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。 偷窃到的最高金额 = 1 + 3 = 4 。

示例 2：

输入：[2,7,9,3,1] 输出：12 解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。 偷窃到的最高金额 = 2 + 9 + 1 = 12 。

tag

动态规划

解题思路

这道 题目 和 Leetcode 第70题 - [爬楼梯] 类似,根据题目的定义,我们 只能找相邻元素.

你偷 了 第一个房子 那么要偷下一个房子的范围 [3,n-1]

假设 你偷了第二间房子 那么要偷的下一房子 范围为 [4,n-1]

以此类推 你偷了第m间房子 那么要偷的下一间房子的范围为[m+2,n-1],

考虑 当偷到 第m间 最大情况为 下一间 是最后一间

另 m + 2 = n -1

得 m = n -3

所以 当 m 为 n-3 时,小偷要偷的下一间房子为 n -1为最后一间,在这之后 小偷去偷 n -2 n-1 就没有符合条件的下一间要偷的房子了.所以只能偷一间。

值的注意的一点是,在计算范围时 如 [3,n-1] ,[4,n-1] 把他们做一下交集就会有公共的部分,每次都去重新计算 会花费大量时间,所以我们就要 把 [m,n-1] 区间的结果 记录起来。

所以 可以得出子问题 ：

v(m) = max{f(m) + v(m+2)}

v(m) 代表第 取第 m 个元素时,再剩下的 m + 2 个 取一个房子取到的最大金额。


#![allow(unused_variables)]
fn main() {
use std::borrow::{Borrow, BorrowMut};
use std::cmp::{max, min};
impl Solution {
pub fn rob(nums: Vec<i32>) -> i32 {
    let mut memory:Vec<i32> =  (0..nums.len()).map(|x| -1).collect();
    helper(nums.as_ref(),0,memory.borrow_mut())
}

}
pub fn helper(nums: &Vec<i32>,index:usize,memory: &mut Vec<i32>)-> i32{
    if index >= nums.len(){
        return 0;
    }

    if memory[index] != -1{
        return memory[index]
    }
    let mut res =0;
    for i in index..nums.len(){
        res = max(res ,nums[i] + helper(nums,i + 2,memory));
    }
    memory[index] = res;
    res
}
}
image-20200708002230627