本文主要是介绍数据结构学习 Leetcode198 打家劫舍，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
动态结构 最长上升子序列
题目：
解法一：
思路：
状态：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]);}
};这篇关于数据结构学习 Leetcode198 打家劫舍的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
