算法-动态规划(一)

• 算法动态规划部分(一),包括 python 源代码

• 参考资料

  https://www.kdaye.com/ap-5ghz-ath10k/

• 更新

  19.02.06 初始
  

导语

• 计划重新整理一遍算法与数据结构,开始选择c实现,但是到了算法部分,这个吐血…
• 无奈用python重写,好处是与伪代码几乎对应.恩,人生苦短,我用python.
• 遂决定把算法部分重刷一遍,希望自己能刷完.

动态规划

概述

• 动态规划简述是 把原问题分解为相对简单的子问题,再依次求解最终解决原问题的方法。
• 许多子问题非常相似,动态规划中某个给定子问题的解已经得出，则存储，以便下次需要同一个子问题解之时直接查表。所以动态规划在输入的规模呈指数增长时特别有用。

• 一个问题是否适用于动态规划求解,取决于 重叠子问题 最优子结构 和 无后效性

  • 最优子结构性质: 问题的最优解所包含的子问题的解也是最优的，可以通过求解子问题的最优解,来求解原问题.
  • 重叠子问题: 在自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规划通过保存已求解的子问题答案,避免冗余计算.
  • 无后效性: 子问题的解一旦确定，就不再改变，不受在这之后、包含它的更大的问题的求解决策影响。

• 动态规划基本求解步骤

  • 分析优化解结构
  • 递归定义最优解代价
  • 自底向上计算最优解代价并保存子问题最优解
  • 根据最优解信息,构造优化解