动态规划
文章目录
该类问题的关键特征:最优子结构,子问题重叠
最优子结构 : 当一个问题的最优解包含这个问题的子问题的最优解, 就称为这个问题具有最优子结构的性质
确定最优子结构的模式:
- 先任意做出第一个决定, 即使这个决定不是最优的
- 确定这个决定之后, 原问题产生了几个子问题
- 一般化从原问题分解为子问题的过程, 确定原问题的最优解涉及多少个子问题
- 确定子问题空间, 自底向上时就是在问题空间中对子问题按照一定顺序进行求解
- 对于子问题空间中的每个子问题, 即每种问题规模下, 需要遍历多少种情况来获取最优解
一般来说, 确定了问题空间和每种空间下的选择, 大致就确定了时间复杂度
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论