动态规划

动态规划

  • 动态规划

  • 阶段: 把所给求解问题的过程恰当地分成若干个相互联系的阶段，以便于求解

  • 状态: 每个阶段面临的条件
  • 无后效性: 过去阶段无法影响现阶段的状态,这意味着过程的历史只能通过当前的状态去影响它的未来的发展，这个性质称为无后效性
  • 最优子结构: 每个阶段的策略都是最优的,称之为最优子策略
  • 状态转移方程: 从k阶段到k + 1 阶段的状态转移规律

    分类

  1. 基本线性动规: 护卫队(单维度)
  2. 背包动规: 「背包九讲」
  3. 区间动规
  4. 双进程动规: 另外增加一个维度表示状态
  5. 树状动规: 在树状图做动态规划

  6. 其他优化

    步骤

  7. 审题

  8. 划分阶段: 根据问题设定的限制条件划分阶段,亦或是按照贪心划分阶段,等等
  9. 设置状态: 设置每个阶段的状态,基本规则是求什么设什么.且满足无后效性
  10. 写出状态转移方程
  11. 运行检查

    参考文章

    大佬的动态规划心得
    %23%20%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%0A%5BTOC%5D%0A%23%23%20%E8%83%8C%E6%99%AF%0A%E8%A7%A3%E5%86%B3%E5%A4%9A%E9%98%B6%E6%AE%B5%E7%9A%84%E6%9C%80%E4%BC%98%E8%A7%A3%E9%97%AE%E9%A2%98%0A%23%23%20%E5%9F%BA%E6%9C%AC%E6%80%9D%E6%83%B3%0A%E5%B0%86%E5%BE%85%E8%A7%A3%E9%97%AE%E9%A2%98%E5%88%86%E8%A7%A3%E4%B8%BA%E8%8B%A5%E5%B9%B2%E4%B8%AA%E5%AD%90%E9%97%AE%E9%A2%98%2C%E4%B8%94%E5%AD%90%E9%97%AE%E9%A2%98%E6%9C%89%E9%87%8D%E5%A4%8D%E6%80%A7%2C%E6%8A%8A%E6%AF%8F%E4%B8%AA%E5%AD%90%E9%97%AE%E9%A2%98%E7%9A%84%E8%A7%A3%E5%A1%AB%E5%85%A5%E8%A1%A8%E6%A0%BC%E4%B8%AD.%0A%23%23%20%E6%A6%82%E5%BF%B5%0A-%20%E9%98%B6%E6%AE%B5%3A%20%E6%8A%8A%E6%89%80%E7%BB%99%E6%B1%82%E8%A7%A3%E9%97%AE%E9%A2%98%E7%9A%84%E8%BF%87%E7%A8%8B%E6%81%B0%E5%BD%93%E5%9C%B0%E5%88%86%E6%88%90%E8%8B%A5%E5%B9%B2%E4%B8%AA%E7%9B%B8%E4%BA%92%E8%81%94%E7%B3%BB%E7%9A%84%E9%98%B6%E6%AE%B5%EF%BC%8C%E4%BB%A5%E4%BE%BF%E4%BA%8E%E6%B1%82%E8%A7%A3%0A-%20%E7%8A%B6%E6%80%81%3A%20%E6%AF%8F%E4%B8%AA%E9%98%B6%E6%AE%B5%E9%9D%A2%E4%B8%B4%E7%9A%84%E6%9D%A1%E4%BB%B6%0A-%20%E6%97%A0%E5%90%8E%E6%95%88%E6%80%A7%3A%20%E8%BF%87%E5%8E%BB%E9%98%B6%E6%AE%B5%E6%97%A0%E6%B3%95%E5%BD%B1%E5%93%8D%E7%8E%B0%E9%98%B6%E6%AE%B5%E7%9A%84%E7%8A%B6%E6%80%81%2C%E8%BF%99%E6%84%8F%E5%91%B3%E7%9D%80%E8%BF%87%E7%A8%8B%E7%9A%84%E5%8E%86%E5%8F%B2%E5%8F%AA%E8%83%BD%E9%80%9A%E8%BF%87%E5%BD%93%E5%89%8D%E7%9A%84%E7%8A%B6%E6%80%81%E5%8E%BB%E5%BD%B1%E5%93%8D%E5%AE%83%E7%9A%84%E6%9C%AA%E6%9D%A5%E7%9A%84%E5%8F%91%E5%B1%95%EF%BC%8C%E8%BF%99%E4%B8%AA%E6%80%A7%E8%B4%A8%E7%A7%B0%E4%B8%BA%E6%97%A0%E5%90%8E%E6%95%88%E6%80%A7%0A-%20%E6%9C%80%E4%BC%98%E5%AD%90%E7%BB%93%E6%9E%84%3A%20%E6%AF%8F%E4%B8%AA%E9%98%B6%E6%AE%B5%E7%9A%84%E7%AD%96%E7%95%A5%E9%83%BD%E6%98%AF%E6%9C%80%E4%BC%98%E7%9A%84%2C%E7%A7%B0%E4%B9%8B%E4%B8%BA%E6%9C%80%E4%BC%98%E5%AD%90%E7%AD%96%E7%95%A5%0A-%20%E7%8A%B6%E6%80%81%E8%BD%AC%E7%A7%BB%E6%96%B9%E7%A8%8B%3A%20%E4%BB%8Ek%E9%98%B6%E6%AE%B5%E5%88%B0k%20%2B%201%20%E9%98%B6%E6%AE%B5%E7%9A%84%E7%8A%B6%E6%80%81%E8%BD%AC%E7%A7%BB%E8%A7%84%E5%BE%8B%0A%23%23%20%E5%88%86%E7%B1%BB%0A%0A1.%20%E5%9F%BA%E6%9C%AC%E7%BA%BF%E6%80%A7%E5%8A%A8%E8%A7%84%3A%20%5B%E6%8A%A4%E5%8D%AB%E9%98%9F%5D(https%3A%2F%2Fwww.cnblogs.com%2Fsmilke%2Fp%2F10502784.html)(%E5%8D%95%E7%BB%B4%E5%BA%A6)%0A2.%20%E8%83%8C%E5%8C%85%E5%8A%A8%E8%A7%84%3A%20%E3%80%8C%E8%83%8C%E5%8C%85%E4%B9%9D%E8%AE%B2%E3%80%8D%0A3.%20%E5%8C%BA%E9%97%B4%E5%8A%A8%E8%A7%84%0A4.%20%E5%8F%8C%E8%BF%9B%E7%A8%8B%E5%8A%A8%E8%A7%84%3A%20%E5%8F%A6%E5%A4%96%E5%A2%9E%E5%8A%A0%E4%B8%80%E4%B8%AA%E7%BB%B4%E5%BA%A6%E8%A1%A8%E7%A4%BA%E7%8A%B6%E6%80%81%0A5.%20%E6%A0%91%E7%8A%B6%E5%8A%A8%E8%A7%84%3A%20%E5%9C%A8%E6%A0%91%E7%8A%B6%E5%9B%BE%E5%81%9A%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%0A6.%20%E5%85%B6%E4%BB%96%E4%BC%98%E5%8C%96%0A%0A%23%23%20%E6%AD%A5%E9%AA%A4%0A1.%20%E5%AE%A1%E9%A2%98%0A2.%20%E5%88%92%E5%88%86%E9%98%B6%E6%AE%B5%3A%20%E6%A0%B9%E6%8D%AE%E9%97%AE%E9%A2%98%E8%AE%BE%E5%AE%9A%E7%9A%84%E9%99%90%E5%88%B6%E6%9D%A1%E4%BB%B6%E5%88%92%E5%88%86%E9%98%B6%E6%AE%B5%2C%E4%BA%A6%E6%88%96%E6%98%AF%E6%8C%89%E7%85%A7%E8%B4%AA%E5%BF%83%E5%88%92%E5%88%86%E9%98%B6%E6%AE%B5%2C%E7%AD%89%E7%AD%89%0A3.%20%E8%AE%BE%E7%BD%AE%E7%8A%B6%E6%80%81%3A%20%E8%AE%BE%E7%BD%AE%E6%AF%8F%E4%B8%AA%E9%98%B6%E6%AE%B5%E7%9A%84%E7%8A%B6%E6%80%81%2C%E5%9F%BA%E6%9C%AC%E8%A7%84%E5%88%99%E6%98%AF%E6%B1%82%E4%BB%80%E4%B9%88%E8%AE%BE%E4%BB%80%E4%B9%88.%E4%B8%94%E6%BB%A1%E8%B6%B3%E6%97%A0%E5%90%8E%E6%95%88%E6%80%A7%0A4.%20%E5%86%99%E5%87%BA%E7%8A%B6%E6%80%81%E8%BD%AC%E7%A7%BB%E6%96%B9%E7%A8%8B%0A5.%20%E8%BF%90%E8%A1%8C%E6%A3%80%E6%9F%A5%0A%0A%23%23%20%E5%8F%82%E8%80%83%E6%96%87%E7%AB%A0%0A%5B%E5%A4%A7%E4%BD%AC%E7%9A%84%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E5%BF%83%E5%BE%97%5D(https%3A%2F%2Fwww.cnblogs.com%2Fsmilke%2Fp%2F10679345.html)