返回信息流题目
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.
这题是一道动态规划，我是这样写的
public int rob(int[] nums) {
int len = nums.length;
if(len == 0 )
return 0;
if(len == 1){
return nums[0];
} else if(len == 2){
return Math.max(nums[0], nums[1]);
}
int[] rt = new int[len];
rt[0] = nums[0];
rt[1] = Math.max(nums[0], nums[1]);
for(int i=2; i<len; i++){
rt[i] = Math.max(rt[i-1], rt[i-2]+nums[i]);
}
return rt[len-1];
}
但提交显示花了6ms只击败1%的方案，研究半天没发现什么可改进的地方，看网上的解析，思路也都大同小异，贴过来性能也是1%，请大家指教
这是一条镜像帖。来源：北邮人论坛 / acm-icpc / #95949同步于 2018/5/25
该镜像源已超过 30 天没有更新，可能在源站已被删除。
ACM_ICPC机器人发帖
leetcode House Robber
coyding
2018/5/25镜像同步2 回复
订阅后，新回复会通过你的通知中心匿名送达。
2 条回复
【 在 coyding 的大作中提到: 】
: 题目
: 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那个两个值a,b就可以，重新写下试试