算法训练营day48_动态规划（3.16提前写）

213.打家劫舍II

围成一圈，关键在于如何解环，转化成一排！

围成一圈之后，与之前不同的地方在于，如果0选了，n-1就选不了了；

分成两种情况：

1. 0选了，1,n-1不选，考虑(2,n-1)左闭右开；
2. 0没选，考虑(1,n)左闭右开；

越界问题搞了我好久。。。左闭右开，有一个元素是l==r-1，如果l>r-1说明一个元素都没，如[2,2)就是一个元素都没；

class Solution {
public:int dp(vector& nums,int l,int r){if(l>r-1) return 0;if(l==r-1) return nums[l];vector f(nums.size());f[l]=nums[l];f[l+1]=max(nums[l],nums[l+1]);for(int i=l+2;i& nums) {int n=nums.size();if (n==1) return nums[0];return max(nums[0]+dp(nums,2,n-1),dp(nums,1,n));}
};

337.打家劫舍III

树形dp，跟没有上司的舞会基本一样；只不过这里是链表构成的树形结构，平时我习惯数组构成树形结构；

这里的节点是T*，舞会节点是数字，这里节点值是t->val，舞会值是数组w[i]；

下标是T*类型，故要开个哈希，f表示没偷，g表示偷了，也可以二维map，我这里不知道咋用哇（OK，查了一下， 就是map套map）

class Solution {
public:unordered_map> f;void dfs(TreeNode* t){f[t][1]=t->val;if(t->left!=NULL){dfs(t->left);f[t][0]+=max(f[t->left][0],f[t->left][1]);f[t][1]+=f[t->left][0];}if(t->right!=NULL){dfs(t->right);f[t][0]+=max(f[t->right][0],f[t->right][1]);f[t][1]+=f[t->right][0];}}int rob(TreeNode* root) {dfs(root);return max(f[root][0],f[root][1]);}
};