IT 面试题库

动态规划适合解决哪类问题?「最优子结构」和「重叠子问题」分别指什么?

中级简答题算法工程师Java后端工程师动态规划最优子结构重叠子问题

题目

考察点:DP 适用性的判断——区别于贪心/回溯的核心特征,以及记忆化如何消除重复计算。

参考答案

内容深度:适中 · 无代码示例 · 来源:外部链接 · 未复核 · 65 天前更新 · 技术内容可能随版本变化,建议结合官方文档理解

核心答案:当一个问题能『分解成同结构的子问题、且子问题被反复计算』时,DP 比暴力递归高效。

要点(两个特征):

要点(与兄弟算法对比):

解题套路:先定义状态 dp[i]、找转移方程、定边界、再考虑空间优化。

练这道题

同分类 · 高频题

题目与答案就在本页;收藏、批注和错题重练在应用内

这道题看完了?连刷同类题,趁热打铁效果最好 进入刷题