LeetCode Day動的プログラミング

198. 住宅強盗

あなたは通り沿いの家々への強盗を計画しているプロの強盗です。各家には一定量の現金が隠されていますが、各家に強盗を防ぐ唯一の制約は、隣接する家にセキュリティ システムが接続されており、同じ夜に隣接する 2 つの家に侵入された場合は自動的に警察に通報されることです。

各家の金額を表す整数配列 nums が与えられた場合、警察に通報せずに今夜強盗できる最大金額を返します。

例 1:

入力: nums = [1,2,3,1]
出力: 4
説明: 家 1 (お金 = 1) を強盗し、次に家 3 (お金 = 3) を強盗します。
強奪できる合計金額 = 1 + 3 = 4.
例 2:

入力: nums = [2,7,9,3,1]
出力: 12
説明: ロブハウス 1 (マネー = 2)、ロブハウス 3 (マネー = 9)、ロブハウス 5 ​​(マネー = 1)。
強奪できる合計金額 = 2 + 9 + 1 = 12.

制約:

1 0 オリジナルページ

    public int rob(int[] nums) {
        int[] dp = new int[nums.length+1];
        dp[1] = nums[0];

        for(int i=2; i<dp.length; i++){
            dp[i] = Math.max(dp[i-2]+nums[i-1], dp[i-1]);
        }
        // System.out.println(Arrays.toString(dp));
        return dp[dp.length-1];

    }

以上がLeetCode Day動的プログラミングの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。