44. LeetCode198. 打家劫舍

• 标签： 动态规划 数组
• 难度： 简单

---

• 题目描述

• 我的解法

设房子编号为 i, 房屋所藏资金为 Mi. 假设我们 挨家挨户 的 上门踩点。

我们先来到 0 号房，我们最多只能偷走 M0 元， R(0) 表示到目前为止(只踩点了 0 号房)，如果我们准备盗窃 0 号房，我们最多能偷走的资金， R(0) = M0

我们接着来到 1 号房， 因为 M1 > M0, 我们最多能偷走 M1 元, R(1) 表示到目前为止(踩点了 0 号房和 1 号房)，如果我们准备盗窃 1 号房，我们最多能偷走的资金，R(1) = M1.

我们接着来到 2 号房，用R(2) 表示到目前为止(踩点了 0 号房， 1 号房， 2 号房)，如果我们准备盗窃 2 号房，我们最多能偷走的资金，R(2) = M2 + R(0)

我们接着来到 3 号房，用R(3) 表示到目前为止(踩点了 0 号房， 1 号房， 2 号房, 3号房)，如果我们准备盗窃 3 号房，我们最多能偷走的资金，R(3) = M3 + max(R(0), R(1))

......

我们来到 i 号房，用R(i) 表示到目前为止(踩点了 0 号房， 1 号房， 2 号房, 3号房.....i号房)，如果我们准备盗窃 i 号房，我们最多能偷走的资金，R(i) = Mi + max(R(0), R(1), ...R(i-2))。

根绝 R(i) 递推式，我们不难实现如下代码 :

import numpy as np
class Solution(object):
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 0
        R = np.zeros(len(nums))
        for i in range(len(nums)):
            if(i==0 or i==1):
                R[i] = nums[i]
            else:
                R[i] = R[0:i-1].max() + nums[i]
        return int(R.max())

• 其他解法

暂略。