[Programming Problem] House Robber

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

Example 1:

Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.

Example 2:

Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
Total amount you can rob = 2 + 9 + 1 = 12.

[Problem Link]

At every step i we have two options:-

Rob current house i and house i-2 …(nums[i] + dp[i-2])
Only rob house i-1, and don’t rob current house …(dp[i-1])

opt(i) = Max(dp[i-1], nums[i] + dp[i-2])

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function(nums) {
    if (nums.length === 0 ) return 0;
    if (nums.length === 1 ) return nums[0];
    if (nums.length === 2 ) return Math.max(nums[0], nums[1]);
 
    const dp = new Array(nums.length);
    dp[0] = nums[0];
    dp[1] = Math.max(nums[0], nums[1]);
    for (let i = 2 ; i < nums.length ; i++ ) {
        dp[i] = Math.max(dp[i-1], nums[i] + dp[i-2]);
    }
    return dp[nums.length-1];
};

Software Everyday – Just another WordPress site

[Programming Problem] Subsets II

Given an integer array nums that may contain duplicates, return all possible subsets (the power set). The solution set must not contain duplicate subsets....

[Programming Problem] Flatten Binary Tree to Linked List

Given the root of a binary tree, flatten the tree into a “linked list”: – The “linked list” should use the same TreeNode class...

[Programming Problem] Largest Number

Given a list of non-negative integers nums, arrange them such that they form the largest number and return it. Since the result may...

[Programming Problem] Sum Root to Leaf Numbers

You are given the root of a binary tree containing digits from 0 to 9 only. Each root-to-leaf path in the tree represents...

[Programming Problem] Reverse Linked List II

Given the head of a singly linked list and two integers left and right where left <= right, reverse the nodes of the list...

[Programming Problem] Jump Game II

Given an array of non-negative integers nums, you are initially positioned at the first index of the array. Each element in the array represents...

[Programming Problem] Find Minimum in Rotated Sorted Array II

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,4,4,5,6,7]...

[Programming Problem] Find Minimum in Rotated Sorted Array

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7]...

[Programming Problem] Print FooBar Alternately

Suppose you are given the following code: class FooBar { public void foo() { for (int i = 0; i < n; i++) {...

[Programming Problem] The Dining Philosophers

[Problem Link] Solution here is to add some `ordering` on the resources (i.e. forks) requested by the processes (i.e. the philosophers). Identify the resource...