Programmation dynamique LeetCode Day

198. Voleur de maison

Vous êtes un voleur professionnel qui envisage de cambrioler des maisons le long d'une rue. Chaque maison a une certaine somme d'argent cachée, la seule contrainte qui vous empêche de cambrioler chacune d'elles est que les maisons adjacentes ont des systèmes de sécurité connectés et elle contactera automatiquement la police si deux maisons adjacentes étaient cambriolées la même nuit.

Étant donné un tableau de nombres entiers représentant le montant d'argent de chaque maison, renvoyez le montant maximum d'argent que vous pouvez voler ce soir sans alerter la police.

Exemple 1 :

Entrée : nums = [1,2,3,1]
Sortie : 4
Explication : Voler la maison 1 (argent = 1) puis voler la maison 3 (argent = 3).
Montant total que vous pouvez voler = 1 + 3 = 4.
Exemple 2 :

Entrée : nums = [2,7,9,3,1]
Sortie : 12
Explication : Voler la maison 1 (argent = 2), voler la maison 3 (argent = 9) et voler la maison 5 (argent = 1).
Montant total que vous pouvez voler = 2 + 9 + 1 = 12.

Contraintes :

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

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

    }

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!