星空网 > 软件开发 > Java

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.

第二遍做法(推荐做法):

DP:我们维护一个一位数组dp,其中dp[i]表示到达 index = i 位置时不相邻数能形成的最大和,i不一定是最后一个rob的房子

dp[0] = num[0];

dp[i] = max(dp[i-1], i>=2? dp[i-2]+num[i] : num[i]);

时间复杂度: O(N), 空间复杂度: O(N) ->O(1)

 1 public class Solution { 2   public int rob(int[] num) { 3     if (num==null || num.length==0) return 0; 4     int[] res = new int[num.length]; 5     res[0] = num[0]; 6     for (int i=1; i<num.length; i++) { 7       res[i] = Math.max(res[i-1], i>=2? res[i-2]+num[i] : num[i]); 8     } 9     return res[num.length-1];10   }11 }

 

第一遍做法:

DP,一维数组dp[i] 表示 以 index = i 房子作为最后一个rob的房子的最大抢劫金额

dp[0] = num[0];

dp[i] = max{dp[0], dp[1], ... dp[i-2]} + num[i];

最后return的是dp[0].....dp[num.length-1]中的最大值

虽然这个思路在这里略麻烦,O(N^2), 但不失为一个好思路

 1 public class Solution { 2   public int rob(int[] num) { 3     if (num==null || num.length==0) return 0; 4     int[] res = new int[num.length]; 5     res[0] = num[0]; 6     if (num.length > 1) res[1] = num[1]; 7     for (int i=2; i<num.length; i++) { 8       int maxVal = 0; 9       for (int j=0; j<i-1; j++) {10         maxVal = Math.max(maxVal, res[j]);11       }12       res[i] = maxVal + num[i];13     }14     int result = 0;15     for (int i=0; i<num.length; i++) {16       result = Math.max(result, res[i]);17     }18     return result;19   }20 }

 




原标题:Leetcode: House Robber

关键词:

*特别声明:以上内容来自于网络收集,著作权属原作者所有,如有侵权,请联系我们: admin#shaoqun.com (#换成@)。
相关文章
我的浏览记录
最新相关资讯
海外公司注册 | 跨境电商服务平台 | 深圳旅行社 | 东南亚物流