动态规划用于求解多阶段决策最优解的问题。
其基本思想与分治法类似，也是将求解问题分解为多个子问题，与分治法不同的是，子问题的求解往往不是相互独立的，若用分治法解决此问题则一个子问题往往被重复计算多次。
如果我们能够保存已解决子问题的答案在需要时能供我们查询就可以避免大量的重复计算。所以动态规划的基本思路是只要子问题被计算解决过就将其记录下来而不管该子问题以后是否被用到。
基本概念
动态规划本质上是多阶段决策问题，在每个阶段都需要作出决策，而该决策又会影响到下一阶段的决策，从未决定了一个问题的求解过程。
各个阶段的决策构成一个决策序列，一个决策序列表示一个策略。若每个阶段都有若干决策则会形成多个策略供我们选择，每个策略对应一个问题的解，多阶段决策问题就是寻求一个最优解。
最优化原理:作为整个过程的最优策略，它满足：相对前面决策所形成的状态而言，余下的子策略必然构成“最优子策略”。一个问题满足最优化原理也称其拥有最优子结构性质。最优性原理实际上是要求问题的最优策略的子策略也是最优。
动态规划动态规划的基本原理动态规划的运用 1. 动态规划的基本原理 动态规划（Dynamic Programmi...
1. 动态规划算法总结2. 漫画：什么是动态规划？3.算法之动态规划4. 动态规划-算法
从运筹学和算法的角度综合介绍动态规划 算法分类总结动态规划与静态规划的关系浅析静态规划和动态规划动态规划解非线性规...
前言 今天开始学习动态规划，一共有三节，分别是：初识动态规划、动态规划理论、动态规划实战。今天这一节就是初识动态规...
5.动态规划5.1 什么是动态规划？5.2 自底向上的动态规划：5.3 自顶向下的动态规划5.4 0-1背包问题：...
动态规划（Dynamic Programming） 本文包括： 动态规划定义 状态转移方程 动态规划算法步骤 最长...
#动态规划 关于动态规划，先摘一段[wiki][1]的描述： ``` 动态规划（英语：Dynamic progra...
目录 动态规划解决了什么 什么是动态规划 典型的动态规划 1. 动态规划解决了什么 的思想就是将大问题拆分成小问题...
递归解法 动态规划解法1 动态规划解法2
Swift 算法实战：动态规划 Swift 算法实战：动态规划
本文标题：动态规划
本文链接：https://www.haomeiwen.com/subject/xbxgeqtx.html
网友评论