LeetCodeの198. House Robberの解法がわからない

Question

こちらの問題です。

https://leetcode.com/problems/house-robber/

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

わかったこと、わからないこと

動的計画法を利用すると出来そうなことまではわかったのですが、いくつかの回答を見ても理解できませんでした。
どのような部分問題を定義するのかがわかりません。

Answer 1

i番目の家で強盗した場合/しなかった場合での最大獲得金額を記録する変数(r, nr)を用意します。
初期値では一件も強盗していないので、どちらも0で初期化します。

2軒以上連続して強盗することはできないので、1軒目の家が終わったときの獲得金額の最大値は以下のようになります。

• 1軒目で強盗した場合の最大獲得金額 = 0軒目で強盗しなかった場合の最大金額 + 1軒目の家での獲得金額
• 1軒目で強盗しなかった場合の最大獲得金額 = 0件目で強盗した場合としなかった場合の金額の大きい方

これをループで最後の家まで処理すれば、獲得金額の最大値になると思います。
pythonだと以下のようなコードで通りました。

class Solution(object):
    def rob(self, nums):
        r, nr = 0, 0
        for n in nums:
            r, nr = nr + n, max(r, nr)
        return max(r, nr)

Comments

[soo]

理解できました。ありがとうございます！