题目链接

关键词

解析

• 先不考虑围成圈的问题，则定义：dp[i] 表示偷到第i家的最高金额，有:
• 偷第 i 家：dp[i] = dp[i - 2] + nums[i]
• 不偷第 i 家：dp[i] = dp[i - 1]

• 根据 dp[i] 的定义，则 dp[i] = Math.max(dp[i - 2] + nums[i - 2], dp[i - 1])

• 同时，为了方便下标，可以把 dp[] 的前两位空出来，就可以不用考虑下标越界的问题了

• 再考虑围成圈的问题，所谓围成圈，无法就是第一家能不能偷的问题，所以，对于每一间房，都有偷和不偷两种选项
• dp[0][i]：表示不偷第1家，且偷到第 i 家的最高金额
• dp[1][i]：表示偷第1家，且偷到第 i 家的最高金额

代码

相似题目