动态规划一
什么是动态规划： 动态规划(dynamicprogramming)是运筹学的一个分支，是求解决策过程(decisionprocess)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistepdecision process)的优化问题时，提出了著名的最优化原理(principleof optimality)，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。1957年出版了他的名著DynamicProgramming，这是该领域的第一本著作。动态规划的目标： 1、主要用于最优化(最大或最小)问题。 2、目的是找出最优解值(可能有多个最优解)。它是一种思想，在程序设计中，已经抽象为一种程序设计技术。 3、动态规划的实质就是通过保存计算过的状态，来避免递归的重叠子问题，去除冗余计算。主要针对题目类型： 1、最短路径问题； 2、数塔问题 3、01背包问题什么样的题目使用动态规划： 1.具有明显的状态和状态转移方程 可以将一个问题定义成一些子问题，然后用子问题的结果直接计算出这个问题的结果 2.递归搜索中有很多重复搜索 用递归求解的问题，如果状态比较简单，比如只有三个参数，每个数值都是100以内的正整数，然后里边只需要这三个参数，那么我们可以把这些结果记忆下来。（记忆化搜索） 3.一般情况下，动态规划求解的都是求最大值最小值的问题 最优化原理（最优子结构性质） 最优化原理可这样阐述：一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。
