动态规划

打家劫舍

中等#198Java时间 O(n)空间 O(1)

题目要做什么

每间房有一个非负金额,不能同时选择相邻房屋。求能够取得的最大金额。

题目示例输入nums = [2,7,9,3,1]
题目示例输出12

01 为什么这样做

处理当前房屋时,只有两种选择:跳过它,保留前一间的最优值;选择它,把金额加到前两间的最优值。两个变量保存这两个状态。

始终成立的条件

计算当前房屋前,prev1 是前 i 间的最优值,prev2 是前 i−1 间的最优值。

02 看见算法执行

动画与代码同步

修改输入,播放自己的例子

当前使用题目示例
修改输入会改变执行过程;预期输出用于核对结果。
数组 / nums步骤 1
执行状态
本次演示输出播放到最后查看

Solution.java参考解法
1class Solution {2    public int rob(int[] nums) {3        int prev2 = 0, prev1 = 0;4        for (int amount : nums) {5            int current = Math.max(prev1, prev2 + amount);6            prev2 = prev1;7            prev1 = current;8        }9        return prev1;10    }11}

键盘控制:A 后退 · D 前进

编程练习

↑↓ 选择↵ 打开Pagefind 全文检索