198. 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.
题意：小偷去一排房间里偷钱，每个房间的钱数不同，不能同时偷相邻的两家，如何能获得最大的钱数。
转化为编程问题就是，给定一个数组，从数组中取出数值，不同时取出相邻数字，如何保证取出的所有数之和最大。
这是一个动态规划问题，动态规划问题通常用来求解最优化问题，而这类的算法通常有一下几个步骤：
1，刻画一个最优解的结构特征。
2，递归地定义最优解。
3，计算最优解的值，通常是自底向上。
4，利用计算出的信息构造一个最优解。
按照这个解题思路：最优解求法在使用动态规划中有两个应该具备的要素，即最优子结构和子问题重叠。最优解的结构特征应该是怎样的，求这类算法的第一步是刻画最优解的结构，通常如果一个问题的最优解包含子问题的最优解，这样的问题就具有最优子结构性质。这里的结构特征就是，数组中的任意相邻的位置不会被同时选中，最优解包含两种情况，即最后一个元素是选中还是不选中。
第二步，递归的定义最优解，这里假设有数组长度为n，那么这样最优解就是有两种情况，即
Max（n）=max（max（n-1），Max（n-2）+n）
即长度为n获得的最大值，应该是长度为n-1获得的最大值和长度为n-2加最后元素所得最大值 ，两者之中的较大值。
自底向上的算法实现为：
BOTTOM-UP-CUT-ROD(p,n)
1 let Max[0,n] be a new array
2 Max[0]=0;
3 for j= 1 to n
4 Max（j）=max（max（j-1），Max（j-2）+j）
5 Max(j)=Max(j)
6 return Max(n)
代码如下，
public class Solution {
public int rob(int[] num) {
int rob = 0; //max monney can get if rob current house
int notrob = 0; //max money can get if not rob current house
for(int i=0; i<num.length; i++) {
int currob = notrob + num[i]; //if rob current value, previous house must not be robbed
notrob = Math.max(notrob, rob); //if not rob ith house, take the max value of robbed (i-1)th house and not rob (i-1)th house
rob = currob;
}
return Math.max(rob, notrob);
}
}