动态规划

Mike大约 5 分钟

动态规划

动态规划概述

动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。

在现实生活中，有一类活动的过程，由于它的特殊性，可将过程分解成若干个互相联系的阶段，在它的每一个阶段都需要作出决策，从而使整个过程达到最好的活动效果。因此各个阶段决策的选取不能任意确定，它依赖于当前面临的状态，又影响以后的发展。当各个阶段决策确定后，就组成一个决策序列，因而也就确定了整个过程的一条活动路线。这种把一个问题看做是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程，这种问题称为多阶段决策最优化问题。

动态规划算法的基本思想

动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解中得到原问题的解。与分治法不同的是，适用于动态规划求解的问题，经分解后得到的子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。

动态规划算法的基本模型

确定问题的决策对象
对决策过程划分阶段
对各阶段确定状态变量
根据状态变量确定费用函数和目标函数
建立各阶段状态变量的转移过程，确定状态转移方程

动态规划算法的适用条件

最优化原理（最优子结构性质）：整个问题的最优解可以通过求解子问题得到（通过子问题的最优解构造出全局最优解）。
无后效性：将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态。
子问题的重叠性：如果有大量的重叠子问题，可以用空间将这些子问题的解存储下来，避免重复求解相同的子问题，从而提升效率。

习题

动态规划

# 动态规划

# 动态规划概述

# 动态规划算法的基本思想

# 动态规划算法的基本模型

# 动态规划算法的适用条件

# 习题

# 基础题目

# 矩阵

# 背包问题

# 完全背包

# 动态规划在树的应用

# 买卖股票的最佳时间/状态机

# 子序列（不连续）

# 子序列（连续）

# 编辑距离

# 回文

# 动态规划：一维

# 总结

动态规划

动态规划概述

动态规划算法的基本思想

动态规划算法的基本模型

动态规划算法的适用条件

习题

基础题目

矩阵

背包问题

完全背包

动态规划在树的应用

买卖股票的最佳时间/状态机

子序列（不连续）

子序列（连续）

编辑距离

回文

动态规划：一维

总结