[Python]lintcode 392. 打劫房屋假设你是一个专业的窃贼，准备沿着一条街打劫房屋。 算一算，如果今晚去打劫，在不触动报警装置的情况下, 你最多可以得到多少钱
lintcode 392. 打劫房屋
假设你是一个专业的窃贼，准备沿着一条街打劫房屋。每个房子都存放着特定金额的钱。你面临的唯一约束条件是：相邻的房子装着相互联系的防盗系统，且 当相邻的两个房子同一天被打劫时，该系统会自动报警。
给定一个非负整数列表，表示每个房子中存放的钱， 算一算，如果今晚去打劫，在不触动报警装置的情况下, 你最多可以得到多少钱
Code
def houseRobber(self, A):# write your code hereif A is None or len(A)==0:return 0n=len(A)dp=[[0] for _ in range (n+1)]dp[0],dp[1]=0,A[0]for i in range(2,n+1,1):dp[i]=max(dp[i-1],dp[i-2]+A[i-1])return dp[n]
想法
- dp[i]=max(dp[i-1],dp[i-2]+A[i-1])，意义即为，在不选择前i栋而选择前i-1栋（没有选择第i-1栋），与选择i-1栋并且选择前i-2栋，二者之中选择最大值。
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！