（动态规划基础 打家劫舍）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;
}
*/