首页 > 其他分享 >动态规划

动态规划

时间:2022-11-10 16:55:57浏览次数:33  
标签:状态 ... dp 穷举 动态 规划 最值

动态规划

  • 首先,动态规划问题的一般形式就是求最值

  • 既然是要求最值,核心问题是什么呢?求解动态规划的核心问题是穷举。因为要求最值,肯定要把所有可行的答案穷举出来,然后在其中找最值呗。

  • 问题可以千变万化,穷举所有可行解其实并不是一件容易的事,需要你熟练掌握递归思维,只有列出正确的「状态转移方程」,才能正确地穷举。

  • 你需要判断算法问题是否具备「最优子结构」,是否能够通过子问题的最值得到原问题的最值。

  • 动态规划问题存在「重叠子问题」,如果暴力穷举的话效率会很低,所以需要你使用「备忘录」或者「DP table」来优化穷举过程,避免不必要的计算。

动态规划三要素

相关文章