动态规划讲解大全
动态规划（dynamic programming）是运筹学的一个分支，是求解决策过程（decision process）最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程（multistep decision process）的优化问题时,提出了著名的最优化原理(principle of optimality），把多阶段过程转化为一系列单阶段问题,逐个求解,创立了解决这类过程优化问题的新方法--动态规划。1957年出版了他的名著Dynamic Programming，这是该领域的第一本著作。
动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用.例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题,用动态规划方法比用其它方法求解更为方便。
虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划（如线性规划、非线性规划)，只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。
动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。不象前面所述的那些搜索或数值计算那样,具有一个标准的数学表达式和明确清晰的解题方法。动态规划程序设计往往是针对一种最优化问题，由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特色的解题方法，而不存在一种万能的动态规划算法,可以解决各类最优化问题。因此读者在学习时，除了要对基本概念和方法正确理解外，必须具体问题具体分析处理，以丰富的想象力去建立模型,用创造性的技巧去求解.我们也可以通过对若干有代表性的问题的动态规划算法进行分析、讨论，逐渐学会并掌握这一设计方法。
基本模型
多阶段决策过程的最优化问题。
在现实生活中,有一类活动的过程，由于它的特殊性，可将过程分成若干个互相联系的阶段,在它的每一阶段都需要作出决策，从而使整个过程达到最好的活动效果。当然，各个阶段决策的选取不是任意确定的,它依赖于当前面临的状态，又影响以后的发展，当各个阶段决策确定后，就组成一个决策序列，因而也就确定了整个过程的一条活动路线，如图所示：(看词条图）
C++中的动态规划算法及常见题⽬汇总什么是动态规划在⾯试过程中如果是求⼀个问题的最优解（通常是最⼤值或者最⼩值），并且该问题能够分解成若⼲个⼦问题，并且⼦问题之间好友重叠的更⼩⼦问题，就可以考虑⽤动态规划来解决这个问题。
动态规划的分类 ⼤多数动态规划问题都可以被归类成两种类型：优化问题和组合问题
优化问题 优化问题就是我们常见的求⼀个问题最优解（最⼤值或者最⼩值）
组合问题 组合问题是希望你弄清楚做某事的数量或者某些事件发⽣的概率两种不同动态规划解决⽅案⾃上⽽下：即从顶端不断地分解问题，知道你看到的问题已经分解到最⼩并已得到解决，之后只⽤返回保存的答案即可
⾃下⽽上：你可以直接开始解决较⼩的⼦问题，从⽽获得最⼩的解决⽅案。在此过程中，你需要保证在解决问题之前先解决⼦问题。这种⽅法叫做表格填充法。
常见的动态规划例⼦
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11. 猜数字⼤⼩
1. 裴波那契数列 裴波那契数列就是典型的组合问题，要求出做某事的数量或者概率
问题分析：对于题⽬中的青蛙爬楼梯问题，初试情况下是只有⼀级台阶时，只有⼀种跳法，只有两级台阶时，有两种跳法，当有n级台
阶时，设n级台阶的跳法总数是f(n),如果第⼀步跳⼀级台阶，则和剩下的n-1级台阶的跳法是⼀样的，如果第⼀级跳两级台阶，则和剩下
的n-2级台阶的跳法是⼀样的，因此最终n级台阶的跳法是f(n)=f(n-1)+f(n-2)，即其是可以被分解为更⼩的⼦问题的，下⾯我们以求解f(10)
为例来分析递归的过程
我们从这张图中不难发现，在这棵树中有很多节点都是重复的，⽽且重复节点会随着n的增⼤⽽急剧增⼤，因此我们采⽤⾃顶向下的⽅
式会有很低的效率，因此我们采⽤⾃下⽽上的⽅法，⾸先根据f(1)和f(2)计算出f(3),再根据f(2)和f(3计算出f(4),以此类推求出f(n)
实现的代码如下
1 int jumpFloor(int number) {
动态规划算法详解及经典例题
⼀、基本概念
（1）⼀种使⽤多阶段决策过程最优的通⽤⽅法。
（2）动态规划过程是：每次决策依赖于当前状态，⼜随即引起状态的转移。⼀个决策序列就是在变化的状态中产⽣出来的，所以，这种多
阶段最优化决策解决问题的过程就称为动态规划。
假设问题是由交叠的⼦问题所构成，我们就能够⽤动态规划技术来解决它。⼀般来说，这种⼦问题出⾃对给定问题求解的递推关系中，这
个递推关系包括了同样问题的更⼩⼦问题的解。动态规划法建议，与其对交叠⼦问题⼀次重新的求解，不如把每⼀个较⼩⼦问题仅仅求解⼀
次并把结果记录在表中（动态规划也是空间换时间的）。这样就能够从表中得到原始问题的解。
（3）动态规划经常常使⽤于解决最优化问题，这些问题多表现为多阶段决策。
关于多阶段决策：在实际中，⼈们经常遇到这样⼀类决策问题，即因为过程的特殊性，能够将决策的全过程根据时间或空间划分若⼲个联
系的阶段。⽽在各阶段中。⼈们都须要作出⽅案的选择。我们称之为决策。⽽且当⼀个阶段的决策之后，经常影响到下⼀个阶段的决策，从
⽽影响整个过程的活动。这样，各个阶段所确定的决策就构成⼀个决策序列，常称之为策略。因为各个阶段可供选择的决策往往不⽌⼀个。
因⽽就可能有很多决策以供选择，这些可供选择的策略构成⼀个集合，我们称之为同意策略集合（简称策略集合）。每⼀个策略都对应地确
定⼀种活动的效果。我们假定这个效果能够⽤数量来衡量。 因为不同的策略经常导致不同的效果，因此，怎样在同意策略集合中选择⼀个策
略，使其在预定的标准下达到最好的效果。经常是⼈们所关⼼的问题。我们称这种策略为最优策略，这类问题就称为多阶段决策问题。
（4）多阶段决策问题举例：机器负荷分配问题
某种机器能够在⾼低两种不同的负荷下进⾏⽣产。在⾼负荷下⽣产时。产品的年产量g和投⼊⽣产的机器数量x的关系为g=g(x)，这时的年
完善率为a，即假设年初完善机器数为x，到年终时完善的机器数为a*x(0
的关系为h=h(y)。对应的完善率为b(0
常见的动态规划问题分析与求解
转载⾃：
动态规划（Dynamic Programming，简称DP），虽然抽象后进⾏求解的思路并不复杂，但具体的形式千差万别，找出问题的⼦结构以及通
过⼦结构重新构造最优解的过程很难统⼀，并不像回溯法具有解决绝⼤多数问题的框架（)。为了解决动态规划问题，只能靠多练习、多思
考了。本⽂主要是对⼀些常见的动态规划题⽬的收集，希望能有所帮助。难度评级受个⼈主观影响较⼤，仅供参考。
⽬录（点击跳转）
动态规划求解的⼀般思路：
判断问题的⼦结构（也可看作状态），当具有最优⼦结构时，动态规划可能适⽤。
求解重叠⼦问题。⼀个递归算法不断地调⽤同⼀问题，递归可以转化为查表从⽽利⽤⼦问题的解。分治法则不同，每次递归都产⽣新的
问题。
重新构造⼀个最优解。
备忘录法：
动态规划的⼀种变形，使⽤⾃顶向下的策略，更像递归算法。
初始化时表中填⼊⼀个特殊值表⽰待填⼊，当递归算法第⼀次遇到⼀个⼦问题时，计算并填表；以后每次遇到时只需返回以前填⼊的
值。
实例可以参照矩阵链乘法部分。
1.硬币找零
难度评级：★
假设有⼏种硬币，如1、3、5，并且数量⽆限。请找出能够组成某个数⽬的找零所使⽤最少的硬币数。
解法：
⽤待找零的数值k描述⼦结构/状态，记作sum[k]，其值为所需的最⼩硬币数。对于不同的硬币⾯值coin[0...n]，有sum[k] = min(sum[k-
coin[0]] , sum[k-coin[1]], ...)+1。对应于给定数⽬的找零total，需要求解sum[total]的值。
typedef struct {
int nCoin; //使⽤硬币数量 //以下两个成员是为了便于构造出求解过程的展⽰
int lastSum;//上⼀个状态
int addCoin;//从上⼀个状态达到当前状态所⽤的硬币种类
} state;
state *sum = malloc(sizeof(state)*(total+1));
