leetcode刷题记录

#include <iostream>
#include<algorithm>
#include<vector>
using namespace std;

//写暴力递归回溯搜索时一般从最后一步开始思考
int solve(vector<int> &nums,int idx){
	if(idx<0){
		return 0;
	}
	
	return max(solve(nums,idx-2)+nums[idx],solve(nums,idx-1)); //返回最后一个决策的最大总收益 
	//solve(nums,idx-2) solve(nums,idx-1) 是最后一个决策两个决策收益,也就是说调用solve(nums,a)
	//会返回第a次决策的最大收益即第a+1个商店对应的最大总收益 
}

int main()
{
	vector<int> nums;
	nums.push_back(1);
	nums.push_back(2);
	nums.push_back(3);
	nums.push_back(1);
//	vector<int> dp(nums.size(),-1); 
	int result=solve(nums,nums.size()-1);
	cout << result << endl;
	system("pause");

	return 0;
}

#include <iostream>
#include<algorithm>
#include<vector>
using namespace std;
vector<int> dp;

//写暴力递归时一般从最后一步开始思考
int solve(vector<int> &nums,int idx){
	if(idx<0){
		return 0;
	}
	if(dp[idx]>=0){
		return dp[idx];//dp[idx]从第一个开始计算,把计算过的直接返回,
		//可以看成最后一个商店对应的最大收益是否被计算过 
	}
	dp[idx]=max(solve(nums,idx-2)+nums[idx],solve(nums,idx-1));////看成计算最后一个商店的最大总收益
	return  dp[idx];//看成最后一个商店的最大总收益的计算结果就行 

}

int main()
{
	vector<int> nums;
	nums.push_back(1);
	nums.push_back(2);
	nums.push_back(3);
	nums.push_back(1);
	
	for (int i=0;i<nums.size();i++){
		dp.push_back(-1);
	} 
	
	int result=solve(nums,nums.size()-1);
	cout << result << endl;
	system("pause");

	return 0;
}

#include <iostream>
#include<algorithm>
#include<vector>
using namespace std;
vector<int> dp;
//递归解法只能从顶到底思考(写暴力递归时一般从最后一步开始思考)
//循环只能从底到顶思考 (倒着搞与前面几步连不上) 

int solve(vector<int> &nums,int idx){
	if(idx==0){
		return 0;
	}
	if(idx==1){
		return nums[0];
	}
	dp[0]=nums[0];
	dp[1]=max(nums[0],nums[1]);
	
	for(int idx=2;idx<nums.size();idx++ ){
		dp[idx]=max(dp[idx-2]+nums[idx],dp[idx-1]);
	}
	
	return  dp[nums.size()-1];

}

int main()
{
	vector<int> nums;
	nums.push_back(1);
	nums.push_back(2);
	nums.push_back(3);
	nums.push_back(1);
	
	for (int i=0;i<nums.size();i++){
		dp.push_back(-1);
	} 
	
	int result=solve(nums,nums.size()-1);
	cout << result << endl;
	system("pause");

	return 0;
}