LeetCode198 House Robber

2937 단어 LeetCode
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.
이 문제는 동적 기획으로 한다.한 거리에 있는 사람들은 모두 일정량의 재산을 가지고 있는데, 만약 두 집과 연결된 물건이 도난당하면 경보를 울릴 것이다.만약 네가 거리의 물건을 훔치러 간다면, 어떻게 경보를 울리지 않는 상황에서 더 많은 것을 얻을 수 있겠는가.구득동태 공식은 i는 i까지 얻은 재산이 가장 많다는 것이다.그러면 얻는 방법은 i집과 i-2집 물건(dp[i-2]+nums[i])을 가지거나 i집을 가지지 않고 i-1집 물건(dp[i-1)을 가지는 것이다. 어느 것이 더 많은지 비교한다.
 1 public class HouseRobber198 {

 2     public int rob(int[] nums){

 3         if(nums == null || nums.length ==0){

 4             return 0;

 5         }

 6         

 7         int[] dp = new int[nums.length +1];

 8         dp[0] = 0;

 9         dp [1] = nums[0];

10         

11         for(int i = 2; i <=nums.length; i++){

12             dp[i] = Math.max(dp[i-2]+nums[i-1], dp[i-1]);

13         }

14         

15         return dp[nums.length];

16     }

17 }

좋은 웹페이지 즐겨찾기