网站建设职员中国旅游网官网

网站建设职员,中国旅游网官网,怎样在门户网站做网络推广,免费搭建wordpress博客题目链接#xff1a;3562. 折扣价交易股票的最大利润#xff08;困难#xff09; 算法原理#xff1a; 解法#xff1a;01背包动态规划 297ms击败34.61% 时间复杂度O(N∗Budget) ①树形结构构建#xff1a;将层级关系#xff08;hierarchy#xff09;转换为邻接表形式的…题目链接3562. 折扣价交易股票的最大利润困难算法原理解法01背包动态规划297ms击败34.61%时间复杂度O(N∗Budget)①树形结构构建将层级关系hierarchy转换为邻接表形式的树形结构节点从 1-based 转为 0-based 索引②后序 DFS 遍历子树对每个节点 x递归处理其所有子节点获取子节点子树的状态数组记录不同预算 j、父节点状态 k 下的最大利润③子树状态合并01 背包采用 01 背包逆序遍历预算的方式将所有子节点的状态数组合并为当前节点的子树合并状态subF表示预算 j、当前节点状态 k 下的子树总利润④当前节点状态计算根据父节点状态 k0/1计算当前节点的购买成本分预算足够 / 不足两种情况取 “不买当前节点” 和 “买当前节点利润为未来价 - 成本” 的最大值生成当前节点的最终状态数组⑤根节点结果提取调用 DFS 处理根节点索引 0返回预算 budget、根节点无父节点状态 0时的最大利润作为答案核心要点用后序 DFS处理树形结构保证先处理子节点再处理父节点用01 背包逆序遍历合并多个子树的状态解决预算分配的优化问题父节点状态影响当前节点的购买成本通过状态数组记录这一依赖关系答疑Q1为什么上面枚举了 subF 这个数组之后下面又要枚举这个 f 的数组这为什么枚举两遍它俩有啥区别吗枚举subF合并子树的背包状态枚举f结合父节点状态推导返回值Java代码class Solution { public int maxProfit(int n, int[] present, int[] future, int[][] hierarchy, int budget) { //构建树形邻接表 ListInteger[] gnew ArrayList[n];//开了大小为n的长度 Arrays.setAll(g,i-new ArrayList()); //员工1对应索引0因为恰好n的大小的空间 for(int[] e:hierarchy) g[e[0]-1].add(e[1]-1); //从根节点开始dfs根节点无父节点状态为未购买0 //f[j][0]:根节点预算j下的最大利润 int[][] f0dfs(0,g,present,future,budget); return f0[budget][0]; } //x:当前处理节点g:树形邻接表present:当前股票价格数组future:股票未来价格数组budget:总预算 private int[][] dfs(int x,ListInteger[] g,int[] present,int[] future,int budget){ //计算从x的所有儿子子树y中能得到的最大利润之和x不买x买 //subF[j][k]:合并x的所有子树后预算j下x自身状态为k时的最大利润 //初始化为0没有子树时利润为0 int[][] subFnew int[budget1][2]; //遍历x的每个直接子节点y合并子树y的状态到subF for(int y:g[x]){ //递归处理子节点y得到y子树的状态数组fy int[][] fydfs(y,g,present,future,budget); //01背包的逆序遍历避免重复选择从大预算到小预算更新 for(int jbudget;j0;j--){ //枚举子树y的预算为jy //当作一个体积为jy价值为fy[jy][k]的物品 //把总预算j拆分成给子树y的运算jy和留给当前节点的剩余预算j-jy来合并子树状态 for(int jy0;jyj;jy) for(int k0;k2;k) //状态转移总预算j剩余j-jy给y的jy //剩余预算j-jy的利润(subF[j-jy][k])y子树预算jy的利润(fy[jy][k]) subF[j][k]Math.max(subF[j][k],subF[j-jy][k]fy[jy][k]); } } //f[j][k]:最终返回的状态数组k表示x的父节点状态 //计算从子树x中能得到的最大利润之和(x父节点不买x父节点买) int[][] fnew int[budget1][2]; for(int j0;jbudget;j){ for(int k0;k2;k){ //k0表示x父节点不买k1表示x父节点买 int costpresent[x]/(k1); if(jcost) //不买x转移源是subF[j][0] //买x转移源是subF[j-cost][1],因为对于子树来说,父节点一定买 f[j][k]Math.max(subF[j][0],subF[j-cost][1]future[x]-cost); else //只能不买x f[j][k]subF[j][0]; } } return f; } }