Rust 力扣 - 198. 打家劫舍
文章目录
- 题目描述
- 题解思路
- 题解代码
- 题目链接
题目描述
题解思路
假设f(i)表示在[1, i]号内的房屋内进行偷盗能够获得的最高金额
存在递推公式
f(i) = max(f(i - 1), f(i - 2) + nums[i])
即f(i)为选择i - 1号房屋的最大金额 和 选择i - 2号房屋的最大金额 的最大值
题解代码
impl Solution {
pub fn rob(nums: Vec<i32>) -> i32 {
let mut n = nums.len();
if n == 1 {
return nums[0]
}
let (mut a, mut b) = (nums[0], nums[0].max(nums[1]));
for i in 2..n {
(a, b) = (b, (a + nums[i]).max(b));
}
b
}
}
题目链接
https://leetcode.cn/problems/house-robber/