House Robber
class Solution {
public:
int rob(vector<int>& nums) {
if(nums.size()==0) return 0;
if(nums.size()==1) return nums[0];
vector<int> sum (nums.size(), 0);
sum[0] = nums[0];
sum[1] = max(nums[1],nums[0]);
for(int i=2;i<nums.size();i++){
sum[i] = max(sum[i-2]+nums[i], sum[i-1]);
}
return sum[nums.size()-1];
}
};
[2,1,1,2] => 并不是每隔一个加一就是最佳
最佳问题=>考虑DP=>思考循环的关联
对于一个nums[i]:
- rob, 那么至此得到的总价是 sum[i-2]+nums[i];
- 不rob, 得到的总价是sum[i-1].
注意sum[0]和sum[1], 如果num[0]>num[1],那到1的时候没有必要rob，直接选择sum[0]。
本来觉得不但要考虑i-1不能rob,还要考虑i+1不能rob，但是实际上可以留给i+1当前点考虑，rob nums[i+1]+sum[i-1];
House Robber II
0 and n-1 is adjacent, then they cannot be chosen both, therefore:
- sum(0 - n-2)
- sum(1 - n-1)
calculate both same as in I.
Longest Increasing Subsequence
- Traditional DP
O(n2） O(n)
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
vector<int> len(nums.size(),1);
for(int i=0;i<nums.size();i++){
for(int j=0;j<i;j++){
if(nums[i]>nums[j]) len[i] = max(len[i], len[j]+1);
}
}
int ma = 0;
for(int i=0;i<len.size();i++){
ma = max(ma, len[i]);
}
return ma;
}
};
- DP with patient sorting
int lengthOfLIS(vector<int>& nums) {
vector<int> res;
for(int i=0; i<nums.size(); i++) {
auto it = std::lower_bound(res.begin(), res.end(), nums[i]);
if(it==res.end()) res.push_back(nums[i]);
else *it = nums[i];
}
return res.size();
}
