（动态规划基础 打家劫舍）leetcode 198

已知h2和h1，用已知推出未知

推是求答案，回溯是给答案
这里图片给出dfs暴力，再进行记录答案完成记忆化搜索，再转为dp数组

#include<iostream>
#include<vector>
#include<algorithm>
//nums:2,1,1,2
//dp:2,2,3,4
using namespace std;
//dp[i]=max(nums[i]+dp[i-2],dp[i-1]);
//nums[i]+dp[i-2]抢这家店
//dp[i-1]不抢这家店



//dfs 暴力+记忆化搜索

int dfs(vector<int>& nums,int n, vector<int>& dp)
{
	if (dp[n]!=-1)//测试用例出现了店里一分钱都没有....
		return dp[n];

	dp[n] = max(dfs(nums, n - 1, dp), dfs(nums, n - 2, dp)+nums[n]);

	return dp[n];

		
	

}

int main()
{
	vector<int>nums = { 0,0,0 };
	if (nums.size() == 1)
	{
		cout << nums[0];
			return 0;
}
	if (nums.size() == 2)
	{
		cout << max(nums[1],nums[0]);
		return 0;
	}
	
	vector<int>dp(nums.size(),-1);
	dp[0]=nums[0];
	dp[1]=(max(nums[0], nums[1]));
	int m = 0;
	m=dfs(nums,nums.size()-1, dp);
	for (auto n : dp)
		cout << n << " ";
	cout << endl;
	cout << m;
}












//dfs暴力
/*
int dfs(vector<int>& nums,int n, vector<int>& dp)
{
	int ans = 0;
	if (n == 1)
		return dp[1];
	if (n == 0)
		return dp[0];
	
	ans= max(dfs(nums, n-1, dp),dfs(nums,n-2,dp)+nums[n]);
	return ans;

}

int main()
{
	vector<int>nums = { 2,1,1,2 };
	if (nums.size() == 1)
	{
		cout << nums[0];
			return 0;
}
	if (nums.size() == 2)
	{
		cout << max(nums[1],nums[0]);
		return 0;
	}
	
	vector<int>dp;
	dp.push_back(nums[0]);
	dp.push_back(max(nums[0], nums[1]));
	int m = 0;
	int sum = 0;
	m=dfs(nums,2,dp);
	cout << m;
}
*/






//标准答案

/*
int main()
{
	vector<int>nums = { 2,1,1,2 };
	vector<int>dp;
	dp.push_back(nums[0]);
	dp.push_back(max(nums[0], nums[1]));
	for (int i = 2;i < nums.size();i++)
	{
		dp.push_back(max(nums[i] + dp[i - 2], dp[i - 1]));

	}
	for (auto n : dp)
		cout << n << " ";
	cout << endl;
	cout << dp[nums.size() - 2];
}

*/

















//自己写的，前n-1项和前n-2项的最大值

/*int main()
{
	//先写dp数组，观察规律
	// 看看能不能从已知推未知，拆子问题
	//打印dp数组
	vector<int>dp;
	vector<int> nums = { 2,1,1,2,2};]
	\

	if (nums.size() == 1)
	{
		cout << nums[0];
		return 0;
	}
	if (nums.size() == 2)
	{
		cout << max(nums[0],nums[1]);
		return 0;
	}
	if (nums.size() == 3)
	{
		cout << max(nums[1],nums[0]+nums[2]);
		return 0;
	}
	int t = nums.size();
	int m = nums[0];
	dp.push_back(nums[0]);
	dp.push_back(nums[1]);
	dp.push_back(nums[2] + nums[0]);
	for (int i = 1;dp.size()!=nums.size();i++)
	{

		m = max(m, dp[i]);
		
		dp.push_back(m + nums[i+2]);


	}
	for (auto n : dp)
		cout << n << " ";
	cout << endl;
    
	cout << max(dp[t - 1], dp[t - 2]);


	return 0;
}
*/