首页 > 数码专栏 > 正文

简述动态规划的四个步骤

数码专栏时间：2024-09-25 07:00:33

图解动态规划的解题四步骤

下面我们一步一步地进行讲解。

步骤一：定义子问题

稍微接触过一点动态规划的朋友都知道动态规划有一个“子问题”的定义。什么是子问题？子问题是和原问题相似，但规模较小的问题。例如这道小偷问题，原问题是“从全部房子中能偷到的最大金额”，将问题的规模缩小，子问题就是“从 k 个房子中能偷到的最大金额”，用 f(k) 表示。

步骤二：写出子问题的递推关系

郑重声明：图文由自媒体作者发布，我们尊重原作版权，但因数量庞大无法逐一核实，图片与文字所有方如有疑问可与我们联系，核实后我们将予以删除。