tag: %u52A8%u6001%u89C4%u5212.md

Tag: 动态规划

3 posts
树形 DP

一句话: DFS 一遍, 每个节点的答案 = 子树聚合 + 自己的贡献。本质是后序遍历 + 状态在节点上传递, 自底向上 return。

...
区间 DP

状态 dp[i][j] 是一段区间的最优答案,转移枚举区间内的”分割点” k。关键不是公式,而是枚举顺序: 必须从短区间到长区间,因为 dp[i][j] 要先有 dp[i][k]dp[k+1][j] 才算得出来。记住这一句,石子合并、戳气球、矩阵链乘就是同一道题。

...
动态规划

DP = 子问题 + 不重复计算。把指数级搜索压成多项式,全靠”算过的别再算”。

...