经典01背包问题
参考大佬题解：
动态规划：01背包问题(无物品价值)，思想相同，题目最终要求有些变化
min为最轻物品的重量，sum为所有物品总重量
假设有一个能装入容量为C(C在[min,sum]间取值)的背包和n件重量分别为w1,w2,…,wn的物品，能否从n件物品中挑选若干件恰好装满背包，要求输出不满足条件的最小容量。
以数组{3,2,5}为例，dp初始化全为0
接下来进行逆序分析：
(逆序是因为同一件物品只能放一次)
(因为分情况时容量要减去当前物品重量，所以高容量的值要用低容量来更新，可能造成重复放入)
(举个例子，判断3是否放入时，如果是顺序的话dp[3]=dp[3]+3放了一次3,之后dp[6]=dp[3]+3又放了一次，就重复了)
判断某一物品能否放入时直接忽略容量小于该物品质量的情况
先判断3是否放入
对于容量为3及以上的都选择放入，对应dp值更新为3
再判断2是否放入
对于容量为5及以上的都选择放入，加上3，对应dp值更新为5
对于容量为3、4的如果放入后剩余容量不够放其他物品，比较3后选择较大值，对应dp值仍为3
容量为2的选择放入，对应dp值更新为2
最后判断5是否放入
对于容量为10的选择放入，加上5，dp值更新为3
对于容量为9的选择放入，加上3， dp值更新为8
对于容量为8的选择放入，加上3， dp值更新为8
对于容量为7的选择放入，加上2， dp值更新为7
对于容量为6的选择放入，dp值更新为5
对于容量为5的选择放入，dp值更新为5
在前i个状态下的最值的前提下，考虑第i个值是否使用，从而把前i个状态的最值求出来,这就是动态规划的思想
思路总结：
j表示背包空间大小，逆序更新是因为要用小的背包更新大的
核心：如果当前背包承重<放入物品最大承重，则更新dp[j] < dp[j - arr[i]] + arr[i]，dp[j - arr[i]]表示背包不放arr[i]时的最大重量
最后当承重为n时，放入的重量不为n则认为是最大不可求和
class Solution { public: int getFirstUnFormedNum(vector<int> arr, int len) { int sum = 0, min = arr[0]; for (int i = 0; i < len; ++i) { sum += arr[i]; if (arr[i] < min) min = arr[i]; } vector<int> dp(sum + 1, 0); for (int i = 0; i < len; ++i) { //j:背包空间大小 //dp[j]:背包最大承重 for (int j = sum; j >= arr[i]; --j) { //dp[j-arr[i]]意思是背包承重为j时， //如果已经放置了arr[i]的重量后还能放置的最大重量 if (dp[j - arr[i]] + arr[i] > dp[j]) dp[j] = dp[j - arr[i]] + arr[i]; } } //最后当承重为n时，放入的重量不为n则认为是最大不可求和 for (int i = min; i <= sum; ++i) { if (i != dp[i]) return i; } return sum + 1; } };
二叉树遍历与构造（考研重点）
核心思想：
根据root节点，将中序vector划分成vin_left，vin_right两部分中序子序列
根据中序子序列长度，将前序vector划分成pre_left, pre_right对应的前序子序列
root->left递归生成
root->right递归生成
具体做法：
step 1：先根据前序遍历第一个点建立根节点。
step 2：然后遍历中序遍历找到根节点在数组中的位置。
step 3：再按照子树的节点数将两个遍历的序列分割成子数组，将子数组送入函数建立子树。
step 4：直到子树的序列长度为0，结束递归。
难点：
对于dfs的pre_strat和pre_end，如上图所示，我们拿左子树left举例
pre_start==preStart+1；（对应前序的元素2）
pre_end==preStrat+（中序根节点 i 左边的所有元素）==preStart+（i-vinStart）；（对应前序的元素7）
其余确定范围的方式同理
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: TreeNode* dfs(vector<int> pre,int preStart,int preEnd,vector<int> vin,int vinStart,int vinEnd) { if(preStart>preEnd||vinStart>vinEnd) return nullptr; TreeNode* root=new TreeNode(pre[preStart]); for(auto i=vinStart;i<=vinEnd;i++) { if(vin[i]==pre[preStart]) { root->left=dfs(pre,preStart+1,preStart+i-vinStart,vin,vinStart,i-1); root->right=dfs(pre,preStart+i-vinStart+1,preEnd,vin,i+1,vinEnd); break; } } return root; } TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) { if(pre.empty()||vin.empty()) return nullptr; return dfs(pre,0,pre.size()-1,vin,0,vin.size()-1); } };
