Skip to content

213 house robber ii

213. House Robber II

题目: https://leetcode.com/problems/house-robber-ii/

难度: Medium

思路:

跟house robber 1 类似,但是加了一些限制,抢到第 n-1 家最大两种可能,抢第 n-1 家和不抢第 n-1 家。

0,  1, 2, 3, 4, 5, 6 ... n-1

所以状态转移方程写成二维的更好来求,从第i家抢到第j家的状态转移方程

            nums[j] ,j = i
dp[i][j] = max(nums[i], nums[i+1]) , j = i +1
            max(dp[i][j-2] + nums[j], dp[i][j-1]), j > i+1

Show me the code

AC代码

class Solution(object):
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        if n == 0 : return 0
        if n == 1 : return nums[0]
        if n == 2 : return max(nums[0],nums[1])

        dp = [[0 for i in range(n)] for j in range(n)]

        for i in range(n):
            for j in range(i,n):
                if j == i:
                    dp[i][j] = nums[j]
                elif j == i + 1:
                    dp[i][j] = max(nums[i],nums[i+1])
                else:
                    dp[i][j] = max(dp[i][j-2] + nums[j], dp[i][j-1])

        # print dp 
        # rob without n-1, or rob with  n-1
        val = max(dp[0][n-2], dp[1][n-3] + nums[n-1])

        return val



回到顶部