algorithm - LeetCode之 "House Robber"路径问题——无法打印路径

Question

我已经解决了LeetCode's "House Robber" problem ，但我无法打印路径。我尝试了一些使用列表的技巧，但总是得到错误的答案。我如何记住之前的决定并删除元素并将元素添加到列表以拥有房屋列表？

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

原来的问题是here

您可以使用数组 path[] 来记住上一步。在这种情况下，path[i] 表示我们从中到达 i 的索引。

在下面的代码中，res 存储了强盗的最终路径(从 1 开始的索引)。以nums = [3,6,2,4,5]为例。 路径[] 将为[-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];
        }
    }
}