(DP)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 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차원수 그룹을 주고 저장된 것은 모두 정수이며 비연속의 최대 합을 구한다.
풀기:
이 문제는 1차원 단순 DP 문제에 속하는데, 유사 구수 그룹의 연속이 가장 크고,
렌을 수조의 길이로 설정하고nums수조는 모든 예금을 저장하며,re수조는 대응하는 길이의 수조의 최대 비연속과,즉re[i]의 값을 저장하고,수조의 길이가 i일 때의 비연속이 가장 크다.
예:
index       0　　1　　 2       3       4
nums 　　5　　 2　　 4　　 7　　 1re　　　　5 　　 5 　  9 　　12     12
len　　     1       2      3       4       5
 
상태 전환:
가령 r[n]을 요구한다면 인접한 값을 얻을 수 없기 때문에 이때는 반드시 r[n-2]를 고려해야 하기 때문에 r[n]=max(re[n-1],nums[n-1]+re[n-2])
초기 상태:
len=1, re[1]=nums[0]
len=2, re[2]=max(re[1], nums[1]+0)
len=3, re[3]=max(re[2], nums[2]+re[1])
...
 
 
위에서 볼 수 있는 현재len=n은re수조의re[n-1],re[n-2]에서만 얻을 수 있기 때문에 두 개의 값으로 앞의 두 상태를 저장할 수 있다.
 
Java 코드:

public class Solution {
    public int rob(int[] nums) {
        if(nums == null || nums.length == 0) return 0;
        int a = 0, b = 0, tmp;              
        for(int i = 0; i<nums.length; i++){
            tmp = b;
            b = nums[i] + a > b ? nums[i] + a : b;
            a = tmp;
        }
        return b;
    }
}

 
파이썬 코드:

class Solution:
    # @param {integer[]} nums
    # @return {integer}
    def rob(self, nums):
        a = b = 0
        for i in xrange(len(nums)):
            a, b = b, max(nums[i] + a, b)
        return b