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. |
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]; }; |
Skip to content
Just another WordPress site
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...