LeetCode DayDynamic Programming

198. Perompak Rumah

Anda seorang perompak profesional yang merancang untuk merompak rumah di sepanjang jalan. Setiap rumah mempunyai sejumlah wang yang disimpan, satu-satunya kekangan yang menghalang anda daripada merompak setiap rumah ialah rumah bersebelahan mempunyai sistem keselamatan yang disambungkan dan ia akan menghubungi polis secara automatik jika dua rumah bersebelahan dipecah masuk pada malam yang sama.

Memandangkan nombor tatasusunan integer yang mewakili jumlah wang setiap rumah, pulangkan jumlah maksimum wang yang anda boleh rompak malam ini tanpa memaklumkan kepada polis.

Contoh 1:

Input: nums = [1,2,3,1]
Keluaran: 4
Penjelasan: Rompak rumah 1 (wang = 1) dan kemudian rompak rumah 3 (wang = 3).
Jumlah amaun yang anda boleh rompak = 1 + 3 = 4.
Contoh 2:

Input: nombor = [2,7,9,3,1]
Keluaran: 12
Penjelasan: Rompak rumah 1 (wang = 2), rompak rumah 3 (wang = 9) dan rompak rumah 5 (wang = 1).
Jumlah amaun yang anda boleh rompak = 2 + 9 + 1 = 12.

Kekangan:

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

    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];

    }

Atas ialah kandungan terperinci LeetCode DayDynamic Programming. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!