【算法日记】Day 13 动态规划专题——树状DP基础

张开发
2026/4/13 0:46:32 15 分钟阅读

分享文章

【算法日记】Day 13 动态规划专题——树状DP基础
Abstract#动态规划#树状DP1. 题目题目LeetCode 1373. 二叉搜索子树的最大键值和核心思路树形DP每个节点返回一个结构体Info包含子树的最小值、最大值、是否为BST、子树节点和、子树中最大BST的键值和。合并时根据左右子树信息判断当前子树是否为BST。如果是BST则当前子树和为左右子树和加当前值并更新最大BST和为三者最大值否则最大BST和取左右子树的最大值。复杂度时间复杂度O ( n ) O(n)O(n)空间复杂度O ( h e i g h t ) O(height)O(height)递归栈。2. 代码classSolution{public:structInfo{intmaxVal,minVal;boolisBst;intsumVal;intmaxBstVal;};constintMIN0xc0c0c0c0;constintMAX0x3f3f3f3f;Infof(TreeNode*x){if(xNULL)return{MIN,MAX,true,0};Info lInfof(x-left);Info rInfof(x-right);intmaxValmax(x-val,max(lInfo.maxVal,rInfo.maxVal));intminValmin(x-val,min(lInfo.minVal,rInfo.minVal));boolisBstlInfo.isBstrInfo.isBstlInfo.maxValx-valrInfo.minValx-val;intsumVallInfo.sumValrInfo.sumValx-val;intmaxBstVal;if(isBst){maxBstValmax(sumVal,max(lInfo.maxBstVal,rInfo.maxBstVal));}else{maxBstValmax(lInfo.maxBstVal,rInfo.maxBstVal);}return{maxVal,minVal,isBst,sumVal,maxBstVal};}intmaxSumBST(TreeNode*root){returnf(root).maxBstVal;}};3. 心得树状DP基础思路所有结点“一视同仁”分析父结点和子树之间的依赖关系。取所有子树所需信息的并集作为递归函数的参数集和返回集。父结点接收到子树信息根据依赖关系处理得到的返回值。边界值设置空节点返回maxVal -INF极小值minVal INF极大值这样在合并时max(lInfo.maxVal, rInfo.maxVal)不会影响正常节点min同理。同时isBst truesumVal 0。4. 相关题目LeetCode 543. 二叉树的直径

更多文章