LeetCoding Challenge Oct. 14: House Robber II

LeetCode October Challenge の 14 日目。

今日の問題は House Robber II。

問題の概要

• House Robber の派生系
  • 与えられた数値の配列より、添字的に隣り合った数値をピックアップしないようにしつつ、ピックアップした数値の合計を最大化したい
• House Robber II では、配列がリング状になっている (すなわち配列先頭は配列末尾と隣合わせになっている) という制約が加わる
  • ピックアップした数値の合計を最大化する点においては変わりはない

考え方

• この手の問題はどうも苦手意識がある… 😧
  • House Robber のときは、「一つ前の数値をピックアップした」と「一つ前の数値をピックアップしなかった」という ２ つの状態をもつステートマシン (?) を使って解いた気がするなあ…
    • このステートマシンを使うアプローチは動的計画法らしい
• 今回の問題もステートマシンを適用できるのだろうか？ 🤔
  • 「先頭の数値はピックアップできるが、末尾の数値はピックアップできない」パターンと、その逆に「先頭の数値はピックアップできないが、末尾の数値はピックアップできる」パターンでそれぞれステートマシンを用いて解を求めればよかったりする？
    • つまりは nums[0 ... nums.length - 1] と nums[1 ... nums.length] という 2 つのパターン、ということ
  • このアルゴリズムの時間計算量は O(n)、空間計算量は O(1)
• とりあえず実装してみよ → submit → 1 回 wrong answer になったけど修正して accept 😊
  • アプローチは間違っていなかったようだ
  • Runtime は 0ms だけど、1ms 以上になるような submit はないようだ…

コード

class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        if (nums.length == 1) {
            return nums[0];
        }
        if (nums.length == 2) {
            return Math.max(nums[0], nums[1]);
        }
        if (nums.length == 3) {
            return Math.max(nums[0], Math.max(nums[1], nums[2]));
        }

        return Math.max(calculate(nums, 0, nums.length - 1),
                calculate(nums, 1, nums.length));
    }

    int calculate(int[] nums, int fromIndex, int toIndex) {
        int robbed = nums[fromIndex];
        int skipped = 0;

        for (int i = fromIndex + 1; i < toIndex; i++) {
            int nextRobbed = skipped + nums[i];
            int nextSkipped = Math.max(skipped, robbed);

            robbed = nextRobbed;
            skipped = nextSkipped;
        }

        return Math.max(robbed, skipped);
    }
}