定义
动态规划（dynamic programming, DP) 是运筹学的一个分支，是求解决策过程最优化的过程。是一种解决问题的方法，也可定义为一种数学模型。在20世纪50年代初，由美国数学家贝尔曼等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理，从而创立了动态规划。
基本原理
有一类活动，可以将过程分为若干个互相联系的阶段，每个阶段做出决策，从而使得整个过程有最好的效果。各个阶段决策的选取依赖当前的状态，还影响以后的发展。通过各个阶段组成的决策序列确定整个过程的一条活动路线，把问题看作一个前后关联具有链状结构的多阶段过程就叫做多阶段决策问题。
在多阶段决策问题中，各个阶段采取的决策，一般来说是与时间有关的，决策依赖于当前状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，称这种解决多阶段决策最优化的过程为动态规划方法。
基本思想
动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。
其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
各个子问题不是相互独立的。为了避免子问题的重复计算，我们使用一个表来记录所有已求解的子问题的结果，称为记忆化存储。这是动态规划的基本思路。具体的动态规划算法多种多样，但都有相同的填表格式。
三大重要性质
- 最优子结构性质：一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。
- 子问题重叠性质：有些子问题在递归算法自顶向下求解过程中，有些会被重复计算。动态规划算法的关键在于解决冗余，这是动态规划算法的根本目的。动态规划实质上是一种以空间换时间的技术，它在实现的过程中，不得不存储产生过程中的各种状态，所以它的空间复杂度要大于其他的算法。选择动态规划算法是因为动态规划算法在空间上可以承受，而搜索算法在时间上却无法承受，所以我们舍空间而取时间。
- 无后效性： 过程的历史只能通过当前的状态去影响它的未来的发展。每个状态都是过去历史的一个完整总结。如果给定某一阶段的状态，则在这一阶段以后过程的发展不受这阶段以前各段状态的影响，所有各阶段都确定时，整个过程也就确定了。
分类
根据决策过程的演变可分为确定性或者随机性。
按照时间参量可分为离散或者连续的变量。
所以有四种：离散确定性、离散随机性、连续确定性、连续随机性四种决策过程模型。
使用场景
应用广泛，包括工程技术、经济、工业生产、军事以及自动化控制等领域，并在背包问题、生产经营问题、资金管理问题、资源分配问题、最短路径问题和复杂系统可靠性问题等中取得了显著的效果。
局限性
- 没有统一的处理方法，具体问题具体性质和技巧来分析和处理
- 变量的维数越大，总的计算量和存储量变大。受存储空间和计算速度的限制，即‘维数障碍’
以上仅供学习，如侵权请联系！！！
网友评论