Kiner算法刷题记(十九):动态规划(算法基础篇)

系列文章导引

  • 系列文章导引

开源项目

本系列所有文章都将会收录到GitHub中统一收藏与管理,欢迎ISSUEStar

GitHub传送门:Kiner算法算题记

前言

我们之前学习了递推算法和地推套路,也说过了递推算法与动态规划暧昧不清的关系,那么,今天就来初步的学习一下动态规划。

状态转移方程

我们之前学习递推算法时所使用的递推公式,在动态规划中叫做:状态转移方程

重点

  1. 状态:一个数学符号加上语义描述
  2. 决策:从所有可能产生最优解的答案当中找出一个最大值或最小值。(动态规划的重点就在于决策,如果一个算法,不需要决策就能得到最优解,这类算法称为贪心算法,至于什么是贪心算法不在我们今天的讨论范畴,我们暂且略过,之后再一起学习。)
  3. 阶段:当前阶段仅仅依赖上一个阶段

递推问题的求解方向

  • 我(目标值)

你可能感兴趣的