LeetCode Day動態編程

198.入室竊盜

你是一名職業強盜，計劃搶劫街道上的房屋。每棟房子都藏有一定數量的錢，唯一阻止你搶劫的限制是相鄰的房子都有安全系統連接，如果相鄰的兩棟房子在同一天晚上被闖入，它會自動聯繫警方。

給定一個代表每棟房子的金額的整數數組 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中文網其他相關文章！