[Dynamic Programming] 198. House Robber
2024-08-31 12:20:56
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.
Input: [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.Input: [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
Total amount you can rob = 2 + 9 + 1 = 12.
1 Form bottom-up approach
/**
* @param {number[]} nums
* @return {number}
*/ var rob = function(nums) {
// if there is nothing, return 0
if (nums.length === ) {
return ;
} // if there is only one value, return itself
if (nums.length === ) {
return nums[];
} // if there are two values, return the larger one
if (nums.length === ) {
return Math.max(nums[], nums[]);
} // if there are more than two values
// copy the nums and preappend leading zero
// to avoid extra if else check for sums[i - 3],
// which can be out of index error
let sums = [].concat(nums); for (let i = ; i < sums.length; i++) {
sums[i] = Math.max(sums[i - ] + sums[i], sums[i - ] + sums[i]);
} return Math.max(
sums[sums.length - ],
sums[sums.length - ]
)
};
2. Recursive:
var rob = function(nums) {
const helper = (nums, i, sums) => {
// if there is nothing, return 0
if (nums.length === ) {
return ;
}
if (nums.length === ) {
return nums[];
}
if (nums.length === ) {
return Math.max(nums[], nums[]);
}
// if there is only one value, return itself
if (i === ) {
sums[] = nums[];
return helper(nums, i+, sums);
}
// if there are two values, return the larger one
if (i === ) {
sums[] = Math.max(nums[], nums[]);
return helper(nums, i+, sums);
}
if (i >= nums.length) {
return Math.max(sums[sums.length - ], sums[sums.length - ]);
}
const step1 = sums[i-] + nums[i];
const step2 = ( sums[i-] || ) + nums[i];
const larger = Math.max(step1, step2);
sums[i] = larger;
return helper(nums, i+, sums);
};
return helper(nums, , []);
}
最新文章
- 基于InstallShield2013LimitedEdition的安装包制作
- fedora22,fedora24最简单的安装virtaulbox的方法
- node.js之开发环境搭建
- StackGAN: Text to Photo-realistic Image Synthesis with Stacked Generative Adversarial Networks 论文笔记
- 禁止复制放在js文件中
- JS鼠标移入，移出事件
- 【JavaScript回顾】对象创建的几种模式
- Linux-wget/tar/ln 函数
- web 缓存
- Java学习疑惑(8)----可视化编程, 对Java中事件驱动模型的理解
- 在H3C交换机上开通一个VLAN并且开通一个端口ping通它
- day02 格式化字符串
- jquery怎么实现点击一个按钮控制一个div的显示和隐藏
- angularjs为ng-click事件传递参数
- CodeForces - 710F：String Set Queries （二进制分组 处理 在线AC自动机）
- WinForm中执行JS代码（多种方法）
- 猴哥来了-游戏开发记录17-微信排行榜bug
- spring boot 自定义视图路径
- metasploit framework（八）：snmp扫描，暴力破解
- UICollectionView 常用操作