题解 | #打家劫舍(一)#

很简单的dp，设定dp[i]为偷窃到第i家为止不被发现的做多的钱，状态转移方程如下：

$dp[i]=max\{dp[i-1],nums[i]+dp[i+2]\}dp[i]=max\backslash \{dp[i-1],nums[i]+dp[i+2]\; \backslash \}$

其实就是每次有两种可能性，偷第i家伙不偷第i家，偷的话就肯定不能偷i-1家了，因此是dp[i-2]+nums[i]，不偷的话最大就是dp[i-1]。

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param nums int整型一维数组 
# @return int整型
#
class Solution:
    def rob(self , nums) -> int:
        # write code here
        # 初始化dp
        dp = [0]*len(nums)
        for i in range(len(nums)):
            if i <= 1:
                dp[i] = max(nums[:i+1])
            else:
                dp[i] = max(dp[i-1] , dp[i-2] + nums[i])
        return max(dp)

nums = [2,10,5]
print(Solution().rob(nums))