DP

对于第i个状态（房子），有两种选择：偷（rob）、不偷（not rob）

递推公式为：

f(i)=max⎧⎩⎨⎪⎪{f(i−1)+vali,f(i−2)+vali,robi−1==0robi−1==1f(i−1),robnot rob

f(i)为动态规划表（DP表）（状态i下的最优解）

val为每间房子里的钱（val表）

rob为记录是否已经偷过，0表示没偷过，1表示偷了（is_robbed表）。

有了递推公式代码就很好写了

class Solution:

    # @param {integer[]} nums

    # @return {integer}

    def rob(self, nums):

        val=[0]+nums

        DP=[0]*(len(nums)+1)

        is_robbed=[0]*(len(nums)+1)

        for i in range(1,len(val)):

            if is_robbed[i-1]==0:

                f_rob=DP[i-1]+val[i]

            else:

                f_rob=DP[i-2]+val[i]

            f_no_rob=DP[i-1]

            if f_rob>f_no_rob:

                DP[i]=f_rob

                is_robbed[i]=1

            else:

                DP[i]=f_no_rob

                is_robbed[i]=0

        return DP[len(nums)]

版权声明：本文为博主原创文章，未经博主允许不得转载。