[TOC]
# 动态规划
**动态规划**(英语:Dynamic programming,简称DP)是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的,通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。
动态规划常常适用于有重叠子问题和最优子结构性质的问题,动态规划方法所耗时间往往远少于朴素解法。
动态规划背后的基本思想非常简单。大致上,若要解一个给定问题,我们需要解其不同部分(即子问题),再根据子问题的解以得出原问题的解。
通常许多子问题非常相似,为此动态规划法试图仅仅解决每个子问题一次,从而减少计算量:一旦某个给定子问题的解已经算出,则将其记忆化存储,以便下次需要同一个子问题解之时直接查表。这种做法在重复 子问题的数目关于输入的规模呈指数增长时特别有用。
## 概述
动态规划在查找有很多**重叠子问题**的情况的最优解时有效。它将问题重新组合成子问题。为了避免多次解决这些子问题,它们的结果都逐渐被计算并被保存,从简单的问题直到整个问题都被解决。因此,动态规划保存递归时的结果,因而不会在解决同样的问题时花费时间。
动态规划只能应用于有**最优子结构**的问题。最优子结构的意思是局部最优解能决定全局最优解(对有些问题这个要求并不能完全满足,故有时需要引入一定的近似)。简单地说,问题能够分解成子问题来解决。
## 适用情况
1. 最优子结构性质。如果问题的最优解所包含的子问题的解也是最优的,我们就称该问题具有最优子结构性质(即满足最优化原理)。最优子结构性质为动态规划算法解决问题提供了重要线索。
2. 无后效性。即子问题的解一旦确定,就不再改变,不受在这之后、包含它的更大的问题的求解决策影响。
3. 子问题重叠性质。子问题重叠性质是指在用递归算法自顶向下对问题进行求解时,每次产生的子问题并不总是新问题,有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质,对每一个子问题只计算一次,然后将其计算结果保存在一个表格中,当再次需要计算已经计算过的子问题时,只是在表格中简单地查看一下结果,从而获得较高的效率。
### 参考
1. [维基百科-动态规划](https://zh.wikipedia.org/wiki/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92)
- 简介
- 零基础快速入门ACM
- C语言快速入门
- C语言快速入门
- C/C++基础
- 输入输出
- 数组和字符串
- 数组
- 字符数组
- 函数和递归
- C++标准容器库(STL)
- Vector
- Map
- Set
- String
- Stack
- Queue
- Priority_queue
- 贪心
- 硬币问题
- 区间调度问题
- 字典序最小问题
- 独木舟问题
- 搜索
- DFS
- BFS
- 剪枝
- 记忆化搜索
- 常用技巧
- 倍增
- 高精度
- 大数加法
- 大数减法
- 大数乘法
- 大数除法
- 大数阶乘
- 输入挂
- 前缀和
- 二分
- 本地预处理
- 尺取
- 枚举
- 坐标离散化
- 分治
- 数列分治
- 树上分治
- 平面分治
- 计算几何
- 凸包
- 点积
- 叉积
- 线段关系
- 皮克定理
- 最近点对
- 数据结构
- 线段树
- 树状数组
- 并查集
- 动态规划
- 基础知识
- 信息学竞赛中的动态规划
- 动态规划初步
- 最长上升子序列(LIS)
- 最长公共子序列(LCS)
- 最大子段和
- 背包问题
- 部分背包
- 0 1 背包
- 完全背包
- 多重背包
- 背包的可行性问题
- 线性DP
- 树形DP
- 区间DP
- 数位DP
- 动态规划优化
- 字符串
- KMP算法
- 拓展KMP
- 字符串Hash
- Manacher算法
- 后缀数组
- Trie树
- 博弈论
- Nim博弈
- Bash博弈
- 斐波那契博弈
- 威佐夫博弈
- SG函数
- 数论
- 整数研究
- 素数判断
- 素数筛选
- 快速幂
- 算数基本定理
- 最大公约数(Gcd)
- 费马小定理
- 扩展欧几里得
- 逆元
- 同余定理
- 组合数学
- 容斥原理
- 抽屉原理
- 卢卡斯(Lucas)
- 卡特兰(Catalan)
- 著名函数
- 欧拉函数
- 莫比乌斯函数
- 线性代数
- 矩阵运算
- 矩阵快速幂
- 图论
- 存图方法
- 邻接矩阵
- 邻接表
- Vector存图
- 链式前向星
- 图的遍历
- 拓扑排序
- 最短路
- Dijkstra算法
- SPFA算法
- Floyed 算法
- 最小生成树
- Prim算法
- Kruskal算法
- 最近公共祖先 (LCA)
- 二分图匹配
- 网络流
- 其他
- 莫队