动态规划

概念

适用于动态规划求解的问题,经过分解得到的问题往往不是相互独立的。若用分治算法来解这类问题,子问题常常被计算多次。动态规划的基本思想是,将计算过的子问题存储到一个表中,来避免重复计算。

动态规划的基本要素

最优子结构:当问题的最优解包含了其子问题的最优解时,称该问题具有最优子结构的性质。
重叠子问题:当采用递归的方式计算问题时,相同的子问题被重复计算多次。

设计动态规划算法的步骤

  • 找出最优解的性质,并刻画其结构特征
  • 递归定义最优值
  • 自底向上的方式计算出最优值
  • 根据计算最优值时得到的信息,构造最优解。
Read more »