LeetCode 하우스 강도 경로

Question

나는이 문제를 해결했지만 패스를 인쇄 할 수 없습니다. 목록을 사용하여 몇 가지 트릭을 시도했지만 항상 잘못된 대답을 얻습니다. 이전 결정을 기억하고 요소를 제거하고 요소를 목록에 추가하여 집 목록을 만들려면 어떻게해야합니까?

public static int rob(int[] nums) { 
    if (nums == null || nums.length == 0) 
     return 0; 

    if (nums.length == 1) 
     return nums[0]; 

    int[] dp = new int[nums.length]; 
    dp[0] = nums[0]; 
    dp[1] = Math.max(nums[0], nums[1]); 

    for (int i = 2; i < nums.length; i++) { 
     dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]); 
    } 

    return dp[nums.length - 1]; 
} 

Answer 1

원래 문제는 이전 단계를 기억하는 배열 path[]을 사용할 수 있습니다 here

입니다. 이 경우 path[i]은 i에 도달하는 색인을 나타냅니다.

아래 코드에서 res은 강도의 최종 경로 (1부터 시작하는 인덱스)를 저장합니다. 예를 들어 nums = [3,6,2,4,5]을 가져 가십시오. path[]은 [-2147483648,-2147483648,0,2,2,3]입니다. 그런 다음 경로를 찾으려면 다시 추적하고 [2,5]이됩니다. 그래서 강도는 2 집과 5 집을 털고 6+5=11을 얻습니다.

public void rob(int[] nums) { 
    if (nums == null || nums.length == 0) return; 
    int[] dp = new int[nums.length + 1]; 
    int[] path = new int[nums.length + 1]; 
    dp[0] = 0; 
    dp[1] = nums[0]; 
    Arrays.fill(path, Integer.MIN_VALUE); 
    for (int i = 2; i <= nums.length; i++) { 
     if (dp[i - 2] + nums[i - 1] > dp[i - 1]) { 
      path[i] = i - 2; 
      dp[i] = dp[i - 2] + nums[i - 1]; 
     } else { 
      path[i] = i - 1; 
      dp[i] = dp[i - 1]; 
     } 
    } 

    LinkedList<Integer> res = new LinkedList<Integer>(); 
    int i = nums.length; 
    while (i > 0) { 
     if (path[i] == i - 1) { 
      i--; 
     } else { 
      res.addFirst(i); 
      i = path[i]; 
     } 
    } 
}