动态结构 最长上升子序列
题目：
解法一：
思路：
状态：F[i]前i间房能偷到的最大金额。
转移方程：
偷和不偷取最大
- 如果不偷：F[i-1]
- 如果偷：nums[i]+F[i-2]如果偷就不能偷前一个，所以要从F[i-2]开始选。
注意这里前一个房子（i-1）偷没偷是不影响这个F[i-2]的，不管怎么样，写F[i-2]就是对的。因为：
如果算F[i-1]的时候，第i-1个房子小偷决定要偷，那么理所当然地，在计算F[i]的时候，如果要偷，必然是要写F[i-2]的（因为要隔着偷）。
如果算F[i-1]的时候，第i-1个房子小偷决定不偷，这个时候，根据转移方程，会有F[i-1]=F[i-2]，那么我们在计算F[i]的时候，如果要偷，nums[i]+F[i-1]和nums[i]+F[i-2]是一样的。
所以不管前一个是偷还是不偷，不管怎么样，写F[i-2]就是对的。
复杂度计算：
时间复杂度O(n)
空间复杂度O(1) （滚动的
代码：
class Solution
{
public:
int rob(vector<int>& nums)
{
if(nums.size()==1) return nums[0];
if(nums.size()==2) return std::max(nums[0],nums[1]);
int dp1=nums[0];
int dp2=max(nums[0],nums[1]);
int f=0;
for(int i=2;i<nums.size();++i)
{
f=std::max(dp1+nums[i],dp2);
dp1=dp2;
dp2=f;
}
return dp2;
}
};
解法二：
思路：
根据最长上升子序列的思路也是可以做的。相对于解法一申请多了一块n大小的vector。
状态：在第i个房间要偷的情况下，F[i]前i间房能偷到的最大金额。
转移方程：F[i]=nums[i]+max(F[0...i-2])（接着前面偷的最赚的方案max(F[0...i-2]))继续偷+nums[i]）
不过如果按照最原始的最长上升子序列来做，每个状态都需要遍历一次前i-1个状态找到最大值，可以用一个max记录前i-3个状态的最大值max，然后比较这个max和F[i-2]谁大，将这个比较出来的结果：F[i]=nums[i]+max(max，F[i-2]) 得到F[i]。
别忘了更新max=max(max，F[i-2])。
复杂度计算：
时间复杂度O(n)
空间复杂度O(n)
其实这个vector也是可以优化掉的，弄成滚动数组就可以了。
代码：
class Solution
{
public:
int rob(vector<int>& nums)
{
vector<int> dp(nums.size());
if(nums.size()==1) return nums[0];
if(nums.size()==2) return std::max(nums[0],nums[1]);
dp[0]=nums[0];
dp[1]=std::max(nums[0],nums[1]);
int max=dp[0];//前i-2个的最大值
for(int i=2;i<nums.size();++i)
{
dp[i]=max+nums[i];
max=std::max(dp[i-1],max);
}
return std::max(max,dp[nums.size()-1]);
}
};
