Leetcode - House Robber

[题目] 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.

[分析]

一维动态规划，记num[i]对应的最大安全盗金为safe[i], 递推式为safe[i] = max(safe[i-1], safe[i-2] + num[i])。

实现时仅需一个三元数组，循环使用.

// version1: 思路不够清晰准确，递推式写错但撞大运实现ok，可读性不好的初版
// 后追加注释
public class Solution {
    public int rob(int[] num) {
        if (num == null || num.length == 0) 
            return 0;
        int safe = 0; // num[i-2] 处能获取的最大盗金，num[i-2]本身不一定被盗
        int adj = 0; // num[i-1]能获取的最大盗金，num[i-1]本身不一定被盗
        int curr = 0; // 盗取num[i]所获的最大盗金
        int max = 0; // num[i]处能获取的最大盗金=max(curr, adj)
        for (int i = 0; i < num.length; i++) {
            curr = safe + num[i];
            if (curr > max)
                max = curr;
            safe = adj;
            adj = max;
        }
        return max;
    }
}

// version 2
// 递推式：safe[i] = max(safe[i-1], safe[i-2] + num[i])
// safe[2]表示num[i]处的最多盗金
// safe[1]表示num[i-1]，即在与num[i]相邻的前面一户能拿的最大盗金
// safe[0]表示num[i-2]处最大盗金
public class Solution {
     public int rob(int[] num) {
        if (num == null || num.length == 0) 
            return 0;
        int n = num.length;
        if (n == 1)
            return num[0];
        else if (n == 2)
            return num[0] > num[1] ? num[0] : num[1];
        
        int[] safe = {num[0], (num[1] > num[0]? num[1] : num[0]), 0};
        for (int i = 2; i < num.length; i++) {
            safe[2] = Math.max(safe[1], safe[0] + num[i]);
            safe[0] = safe[1];
            safe[1] = safe[2];
        }
        return safe[2];
     }
}

    

 

 

评论

4 楼 likesky3 2015-04-03  

赞yb君的代码精简，我会采纳你的意见，面试时可以先写safe[n]版，有时间再向面试官指出可以用更少的空间实现。当知道有更优化的方案时，我总想一次做到，完成时间自然会相应延迟些，我要有意识地培养first work than optimize的意识

3 楼 qb_2008 2015-04-02  

现在看起来好多了！如果想再优化，有一点代码可以去掉。

// 递推式：safe[i] = max(safe[i-1], safe[i-2] + num[i])  
// safe[2]表示num[i]处的最多盗金  
// safe[1]表示num[i-1]，即在与num[i]相邻的前面一户能拿的最大盗金  
// safe[0]表示num[i-2]处最大盗金  
public class Solution {  
     public int rob(int[] num) {  
        if (num == null)   
            return 0;            
        int[] safe = {0, 0, 0};  // Does java initialize variables?: int[] safe = new int[3];
        for (int i = 0; i < num.length; i++) {  
            safe[2] = Math.max(safe[1], safe[0] + num[i]);  
            safe[0] = safe[1];  
            safe[1] = safe[2];  
        }  
        return safe[2];  
     }
}

另外，我感觉面试中更注重时间复杂度，对空间复杂度并不太注意，
所以我会选择直接用safe[n]的数组来递推，这样代码简单，正确性高，完成时间快。

// safe[i] is max amount of money we can rob from [0-i] houses.
// safe[i] = max(safe[i-1], safe[i-2] + num[i])   
public class Solution {  
     public int rob(int[] num) {  
        if (num == null || num.length == 0)   
            return 0;            
        else if (num.length == 1)
            return num[0];
        else if (num.length == 2)
            return Math.max(num[0], num[1]);

        int[] safe = new int[num.length];
        safe[0] = num[0];
        safe[1] = Math.max(safe[0], num[1]);
        for (int i = 2; i < num.length; i++) {
             safe[i] = Math.max(safe[i-1], safe[i-2] + num[i]);
        }  
        return safe[num.length - 1];  
     }
}

2 楼 likesky3 2015-04-02  

谢谢yb君的意见，我自己也觉得没描述清楚，而且递推式确实不准确，已更正

1 楼 qb_2008 2015-04-01  

safe[i]的定义为偷完前i户最大所得值。完整递推式应为safe[i] = max(safe[i - 1], safe[i - 2] + num[i])。
代码中把safe, adj, curr, max四个变量混在一起，着实难以理解。没有注释都看不懂，可不可以让可读性更好些？