House Robber
假设你是一个专业的小偷，打算洗劫一条街所有的房子，每个房子都有价值不同的宝物，但是如果你连续偷了两栋房子，就会触发报警系统，编程求出你最多可以偷窃价值多少的宝物
eg：
[3,4,1,2] -->6 [3,(4),1,(2)]
[4,3,1,2] -->6 [(4),3,1,(2)]
暴力解法
检查所有房子的组合，对每一个组合检查是否有相邻的房子，如果没有，记录其价值，找到最大值。
时间复杂度：O((2^n)*n)
递归树如下
状态转移方程
- 我们称对 ”考虑偷取[x...n-1]范围里的房子“ 的递归函数的定义，我们称之为"状态"
f(0)=max{ v(0)+f(2), v(1)+f(3), v(2)+f(4), ... v(n-3)+f(n-1), v(n-2), v(n-1) }
上面的函数f(x)代表从第x个房子偷取获取宝物的最大值，v(y)代表去除y号房子代表的价值。本题的是考虑从 "0号房子考虑，获取偷取宝物的最大值"，
即，
- 可以是 偷取0号房子的宝物，加上从2号房子考虑偷取宝物的最大值；
- 可以是 偷取1号房子的宝物，加上从3号房子考虑偷取宝物的最大值；
- 可以是 偷取2号房子的宝物，加上从4号房子考虑偷取宝物的最大值；
... - 可以是 偷取n-3号房子的宝物，加上从n-1号房子考虑偷取宝物的最大值；
- 可以是偷取n-2号房子的宝物，加上从n号房子考虑偷取宝物的最大值，以为n号房子不存在，所以忽略。
- 可以是偷取n-1号房子的宝物...
这些方案中选择最大值即为本题的解。也就是上面的方程。该方程我们称之为"状态转移方程"。
递归函数
/**
* 获取宝物的最大值
*
* @param house 房子
* @return 获取宝物的最大值
*/
public int robs(int[] house) {
return tryRobs(0, house);
}
/**
* 尝试抢劫获取宝物的最大值
*
* @param index 开始考虑抢劫房子的编号
* @param house 房子
* @return 尝试抢劫获取宝物的最大值
*/
private int tryRobs(int index, int[] house) {
if (index >= house.length) {
// 尝试抢劫房子的编号超出房子编号的最大值
return 0;
}
// 用于记录本次抢劫房子的最大值
int res = -1;
for (int i = index; i < house.length; i++) {
res = Integer.max(res, house[i] + tryRobs(i + 2, house));
}
return res;
}
记忆化搜索
/**
* 获取宝物的最大值
*
* @param house 房子
* @return 获取宝物的最大值
*/
public int robs(int[] house) {
int[] memo = new int[house.length];
Arrays.fill(memo, -1);
return tryRobsWithMemo(0, house, memo);
}
/**
* 带记忆化搜索的尝试抢劫获取宝物的最大值
*
* @param index 开始考虑抢劫房子的编号
* @param house 房子
* @param memo memo[x]开始考虑抢劫x号房子获取宝物的最大值
* @return 尝试抢劫获取宝物的最大值
*/
private int tryRobsWithMemo(int index, int[] house, int[] memo) {
if (index >= house.length) {
// 尝试抢劫房子的编号超出房子编号的最大值
return 0;
}
if (memo[index] != -1) {
return memo[index];
}
// 用于记录本次抢劫房子的最大值
int res = -1;
for (int i = index; i < house.length; i++) {
res = Integer.max(res, house[i] + tryRobsWithMemo(i + 2, house,memo));
}
memo[index] = res;
return res;
}
动态规划
int rob(int[] house) {
int length = house.length;
if (length == 0) {
return 0;
}
int[] memo = new int[length];
Arrays.fill(memo, -1);
memo[length - 1] = house[length - 1];
for (int i = length - 2; i >= 0; i--) {
// 计算memo[i]的最大值
for (int j = i; j < length; j++) {
memo[i] = Integer.max(memo[i], house[j] + (j + 2 < length ? memo[j + 2] : 0));
}
}
return memo[0];
}
拓展
- 考虑偷取从[x...n-1]范围里的房子的宝物
- 考虑偷取从[0...x]范围里房子的宝物
House Robber II
和Hourse Robber 一样，不过这次实在环形的街道，也就是给定的数组中，第一个元素和最后一个元素为邻居，在不触碰警报的情况下能够窃取财产的最大值是多少？
House Robber |||
和House Robber 一样，不过这次是在一个小区中，整个小区呈二叉树的结构，在不触碰警报的前提下，能够窃取财产的最大值是多少？
eg:3 3 / \ / \ 2 3 4 5 \ \ / \ \ 3 1 1 3 1 最大值为3+3+1=7 最大值为4+5=9
Best Time To Buy And Sell Stock with Cooldown
给定一个数组，表示一只股票在每一天的价格。设计一个交易算法，在这些天进行自动交易，要求：每天只能进行一次操作，在买完股票后，在下一天是不能购买的。问如何交易，能让利益最大化。
eg:
price=[1,2,3,0,2]
最佳交易方式：[buy, sell, colldown, buy, sell],利润为3，算法返回3
网友评论