Blind 75
House Robber
- Problem
- LC 198
- Category
- DP
- File
- blind75_LC198HouseRobber.java
- Path
- pkg5leetcode/blind75/blind75_LC198HouseRobber.java
- Package
- pkg5leetcode.blind75
- Command
- java pkg5leetcode/blind75/blind75_LC198HouseRobber.java
- Approach
- DP rob current + skip prev vs skip current.
- Complexity
- Time O(n), Space O(1)
There is no in-browser runner. This is the file from the curriculum, unchanged.
1package pkg5leetcode.blind75;2 3/*4 * House Robber | LC 1985 * APPROACH: DP rob current + skip prev vs skip current.6 * COMPLEXITY: Time O(n), Space O(1)7 */8public class blind75_LC198HouseRobber {9 static int rob(int[] nums) {10 int prev2 = 0, prev1 = 0;11 for (int x : nums) {12 int cur = Math.max(prev1, prev2 + x);13 prev2 = prev1;14 prev1 = cur;15 }16 return prev1;17 }18 19 public static void main(String[] args) {20 check(rob(new int[]{1, 2, 3, 1}) == 4, "case1");21 check(rob(new int[]{2, 7, 9, 3, 1}) == 12, "case2");22 System.out.println("all tests passed");23 }24 25 static void check(boolean cond, String name) {26 if (!cond) throw new AssertionError("FAILED: " + name);27 System.out.println(" PASS " + name);28 }29}