• 37.9%

https://leetcode.com/problems/house-robber/#/description

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 system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

1. rob(i)表示偷了第i家，notrob(i) 不偷第i家。
2. rob(i) = rob(i-1)+nums[i] ,notrob(i) = max(rob(i-1), notrob(i-1))

rob(i) = max(rob(i-1), notrob(i-1)+nums[i]);

notrob(i) = max(rob(i-1), notrob(i-1));

1. f(i+1) 表示偷到第i家的最大利益, f(0) = 0, f(1) = nums[1]
2. 则f(i+1) = max(f(i), f(i-1)+nums[i])

https://discuss.leetcode.com/topic/32215/c-dp-solution-with-thinking-process-explanation

C++ DP solution with thinking process explanation

Following the same logic described in a post about Best Time to Buy and Sell Stock with Cooldown, we could try to solve this problem with DP.

Define the following variables

rob[i] means max profit for any robbing sequence before house i ending with rob

rest[i] mean max profit for any robbing sequence before house i ending with rest

We could get the following relationship,

Furthermore, we always gain more profit when robbing the house. As a result,

substitute these into the original equations, we get

So we only need two values to keep track of the max profit.

https://discuss.leetcode.com/topic/28369/the-correct-dp-solution

The correct DP solution

Here is the DP formula that leads to the right answer:

M(k) = money at the kth house

P(0) = 0

P(1) = M(1)

P(k) = max(P(k−2) + M(k), P(k−1))

https://discuss.leetcode.com/topic/11110/c-1ms-o-1-space-very-simple-solution

C 1ms, O(1)space, very simple solution

https://discuss.leetcode.com/topic/17199/python-solution-3-lines

Python solution, 3 lines.

Based on the recursive formula:

f(0) = nums[0]

f(1) = max(num[0], num[1])

f(k) = max( f(k-2) + nums[k], f(k-1) )

https://discuss.leetcode.com/topic/12735/c-my-solution-dp

C++,My solution,DP

44ms, 31.77%, 69/69, April.25, 2016

https://leetcode.com/discuss/76958/3-line-python-solution

Python solution, 3 lines.

Based on the recursive formula:

my code

rob[i] = notrob[i-1] + nums[i]

notrob[i] = max(rob[i-1], notrob[i-1])