[アルゴリズム]LeetCode-Houseルータ

LeetCode - 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 systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

I/O例
Example 1:
Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.
Example 2:
Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
Total amount you can rob = 2 + 9 + 1 = 12.
せいげんじょうけん

1 <= nums.length <= 100
0 <= nums[i] <= 400

Solution
[戦略]
DPメソッドの使用
1.各単語をHashMapとして保存します.
2.文字列sを0からjにカットし、HashMapに格納されている単語であることを決定する

の場合、記録2次元配列に0文字目-j文字目として記録されるプリレジストレーション語.
単語

が保存されていない場合はfalse

が保存されます.

文字列の始点(i)が1つ増加するごとに、文字列sの0番目の-i-1が予め登録された単語からなり、2次元配列にtrueとして記録された場合にのみ、2番目のプロセス

が繰り返される.

class Solution {
    public int rob(int[] nums) {

        if (nums.length == 1) {
            return nums[0];
        }

        int twoPrevSum = nums[0];
        int prevSum = Math.max(nums[0], nums[1]);
        int sum = prevSum;

        for (int i = 2; i < nums.length; i++) {
            sum = Math.max(twoPrevSum + nums[i], prevSum);
            twoPrevSum = prevSum;
            prevSum = sum;
        }

        return sum;
    }
}