题解 | 打家劫舍(一)

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型一维数组
     * @return int整型
     */
    public int rob (int[] nums) {
        int[][] dp = new int[nums.length][2];
        dp[0][0] = 0;
        dp[0][1] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (i >= 2) {
                dp[i][1] = Math.max(dp[i - 1][0], Math.max(dp[i - 2][0],
                                    dp[i - 2][1])) + nums[i];
                dp[i][0] = Math.max(dp[i - 1][1], Math.max(dp[i - 2][0], dp[i - 2][1]));
            } else {
                dp[i][1] = dp[i - 1][0] + nums[i];
                dp[i][0] = dp[i - 1][1];
            }
        }
        return Math.max(dp[nums.length - 1][0], dp[nums.length - 1][1]);
    }
}

定义d[i][0]代表第i家不打劫。d[i][1]代表第i家打劫。

当遇到第i家时，有两种情况，打劫和不打劫。

当打劫时，说明前一家不打劫，前两家可能打劫也可能不打劫。

所以有

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

当不打劫时

dp[i][0] = Math.max(dp[i - 1][1], Math.max(dp[i - 2][0], dp[i - 2][1]));

最后只需要输出最后一家打劫和不打劫的最大值即可。

为什么要考虑前两家，因为遇到下面这样的数据，是需要跳过一些数据的，联系两家都不打劫。

[10,1,1,10]

最大值是20，只打劫第一个和最后一个，中间的都不打劫。

为什么不考虑前三个，因为跳过三个一定比不跳过小，因为数据都大于0.

[10,1,1,1,10],最大值10+1+10=21，跳过中间三个10+10=20.