LeetCode198.打家劫舍

 打家劫舍和背包问题一样是一道非常经典的动态规划问题，只要做过几道动态规划的题，这道题简直就非常容易做出来。我应该花了10来分钟左右就写出来了，动态规划问题最重要的就是建立状态转移方程，就是说如何从上一个状态转移到下一个状态的。直观的说就是dp[i]是怎么来的，是通过dp[i-1]来的还是通过dp[i-2]来的等等，如果知道初始状态和状态转移方程，那么每个状态都可以算出来，以下是我的代码：

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        int[][] dp = new int[n][2];
        dp[0][0] = 0;
        dp[0][1] = nums[0];
        int max = Math.max(dp[0][0], dp[0][1]);
        for(int i=1;i<n;i++){
         dp[i][0] = max;
         dp[i][1] = dp[i-1][0]+nums[i];
         max = Math.max(dp[i][0], dp[i][1]);
        }
        return max;
    }
}

 数组大小是n，我建立一个int[n][2]的dp数组，其中dp[i][0]表示不偷第i家能获得的最大的价值，dp[i][1]表示偷第i家能获得的最大的价值。max表是dp[i][0]和dp[i][1]中的最大值，表示偷到第i家能获得的最大价值(因为是从第0家偷到第n-1家的)。

初始状态：dp[0][0]=0; 表示不偷第0家，dp[0][1]=nums[0];表示偷第0家。

状态转移方程：dp[i][0] = max;这个max是dp[i-1]的最大值，就是说如果我不偷第i家，那么第i-1家偷不偷都可以，所以不偷第i家的最大值就是第i-1家的最大值，与偷不偷i-1无关。

dp[i][1] = dp[i-1][0]+nums[i];偷第i家的最大值就是不偷第i-1家的最大值dp[i-1][0]+第i家的价值nums[i];

最后只要返回dp[n-1][0]和dp[n-1][1]中的最大值即可，而max正好是两者中的最大值，所以只要返回max即可。

动态规划问题都是这个套路，找到状态转移方程，通过初始状态算出每个状态，返回最后那个状态或者返回所有状态中的最值。

看看题解有没有新颖的解法。

题解的思路确实更清晰，他dp数组是一维的，没有分什么偷和不偷，dp[i]就表示在第i家的最大价值也就是max，那么状态转移方程就是：dp[i] = Math.max(dp[i – 2] + nums[i], dp[i – 1]);dp[i-2]+nums[i]表示偷第i家，那么就是在第i-2家的最大值家上nums[i]；dp[i-1]就是不偷第i家，那么就是第i-1家的最大值。dp[i]取两者中的最大值即可。

class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int length = nums.length;
        if (length == 1) {
            return nums[0];
        }
        int[] dp = new int[length];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < length; i++) {
            dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
        }
        return dp[length - 1];
    }
}

代码007普通

打赏 收藏 海报 链接