动态规划从入门到精通

动态规划入门1(2008-09-20 21:40:51)第一节动态规划基本概念一，动态规划三要素：阶段，状态，决策。

他们的概念到处都是，我就不多说了，我只说说我对他们的理解：如果把动态规划的求解过程看成一个工厂的生产线，阶段就是生产某个商品的不同的环节，状态就是工件当前的形态，决策就是对工件的操作。

显然不同阶段是对产品的一个前面各个状态的小结，有一个个的小结构成了最终的整个生产线。

每个状态间又有关联（下一个状态是由上一个状态做了某个决策后产生的）。

下面举个例子：要生产一批雪糕，在这个过程中要分好多环节：购买牛奶，对牛奶提纯处理，放入工厂加工，加工后的商品要包装，包装后就去销售……，这样没个环节就可以看做是一个阶段；产品在不同的时候有不同的状态，刚开始时只是白白的牛奶，进入生产后做成了各种造型，从冷冻库拿出来后就变成雪糕（由液态变成固态=_=||）。

每个形态就是一个状态，那从液态变成固态经过了冰冻这一操作，这个操作就是一个决策。

一个状态经过一个决策变成了另外一个状态，这个过程就是状态转移，用来描述状态转移的方程就是状态转移方程。

经过这个例子相信大家对动态规划有所了解了吧。

下面在说说我对动态规划的另外一个理解：用图论知识理解动态规划：把动态规划中的状态抽象成一个点，在有直接关联的状态间连一条有向边，状态转移的代价就是边上的权。

这样就形成了一个有向无环图AOE网（为什么无环呢？往下看）。

对这个图进行拓扑排序，删除一个边后同时出现入度为0的状态在同一阶段。

这样对图求最优路径就是动态规划问题的求解。

二，动态规划的适用范围动态规划用于解决多阶段决策最优化问题，但是不是所有的最优化问题都可以用动态规划解答呢？一般在题目中出现求最优解的问题就要考虑动态规划了，但是否可以用还要满足两个条件：最优子结构（最优化原理）无后效性最优化原理在下面的最短路径问题中有详细的解答；什么是无后效性呢？就是说在状态i求解时用到状态j而状态j就解有用到状态k…..状态N。

动态规划：从新手到专家（转）前言我们遇到的问题中，有很大一部分可以用动态规划(简称DP)来解。

解决这类问题可以很大地提升你的能力与技巧，我会试着帮助你理解如何使用DP来解题。

这篇文章是基于实例展开来讲的，因为干巴巴的理论实在不好理解。

注意：如果你对于其中某一节已经了解并且不想阅读它，没关系，直接跳过它即可。

什么是动态规划，我们要如何描述它?动态规划算法通常基于一个递推公式及一个或多个初始状态。

当前子问题的解将由上一次子问题的解推出。

使用动态规划来解题只需要多项式时间复杂度，因此它比回溯法、暴力法等要快许多。

现在让我们通过一个例子来了解一下DP的基本原理。

首先，我们要找到某个状态的最优解，然后在它的帮助下，找到下一个状态的最优解。

“状态”代表什么及如何找到它?“状态”用来描述该问题的子问题的解。

原文中有两段作者阐述得不太清楚，跳过直接上例子。

如果我们有面值为1元、3元和5元的硬币若干枚，如何用最少的硬币凑够11元？(表面上这道题可以用贪心算法，但贪心算法无法保证可以求出解，比如1元换成2元的时候)首先我们思考一个问题，如何用最少的硬币凑够i元(i<11)？为什么要这么问呢？两个原因：1.当我们遇到一个大问题时，总是习惯把问题的规模变小，这样便于分析讨论。

2.这个规模变小后的问题和原来的问题是同质的，除了规模变小，其它的都是一样的，本质上它还是同一个问题(规模变小后的问题其实是原问题的子问题)。

好了，让我们从最小的i开始吧。

当i=0，即我们需要多少个硬币来凑够0元。

由于1，3，5都大于0，即没有比0小的币值，因此凑够0元我们最少需要0个硬币。

(这个分析很傻是不是？别着急，这个思路有利于我们理清动态规划究竟在做些什么。

) 这时候我们发现用一个标记来表示这句“凑够0元我们最少需要0个硬币。

”会比较方便，如果一直用纯文字来表述，不出一会儿你就会觉得很绕了。

那么，我们用d(i)=j来表示凑够i元最少需要j个硬币。

山东师大附中陈键飞前言自古以来就是NOIP的重要考察内容，在联赛中占的分量大。

对选手能力有一定要求，需要能够熟练地建立动态规划模型。

需要大量做题，初学者不易掌握其思想。

目录基础：基本概念背包问题——一类典型应用 进阶：更多的问题树形DP状态压缩优化：减少状态数目减少状态转移（决策）时间基本概念最长上升子序列状态：f[i]能完全地表示出问题某个或某些本质相同的形态决策：f[i]=min(f[j]+1)状态由哪个状态转移得到阶段：每个i前面的阶段决定后面的阶段，后面的阶段由前面的状态转移得到基本概念石子合并状态f[i,j]决策f[i,j]=min(f[i,k]+f[k+1,j])+w[i,j] 阶段j-i （区间大小）基本概念无后效性后面阶段的状态只受前面阶段的状态的影响 对于任意两个状态，只能单向的进行转移基本概念拓扑图（有向无环图）无后效性f[i]=min(f[j])+1基本概念 非拓扑图（可能有环） 有后效性a →b →c ？b →c →a ？a bc 51111基本概念最优子问题问题最优，只需子问题最优，与到达子问题的路径无关3 5 24 6f(5)最优，只需f(4)最优，与f(4)是怎么到达的无关与路线具体是3 4 6还是2 4 6无关基本概念最优子问题输出1~n中∑(A(i,p[i]))最大的排列f(i)表示用1~n组成的长度为i的序列？ 与到达子问题的路径有关！1 4 3 →6 ？4 2 3 →6 ？基本概念无后效性、最优子问题是否能满足与状态的表示，状态的转移，阶段的划分有关背包问题——一类典型应用 给定n个货币，面值各不相同，问能否凑出m元钱f[i,j]表示前i个货币能否凑出j元f[i,j] = f[i-1,j] （不选j）or f[i-1,j-w[i]]（选j）背包问题——一类典型应用 给定n种货币，每种无限多个，面值各不相同，问能否凑出m元钱f[i,j]表示前i种货币能否凑出j元f[i,j]=f[i-1,j] or f[i,j-w[i]]背包问题——一类典型应用 给定n种货币，第i种有A i个，面值W i，问能否凑出m 元钱将每种货币i拆成A i个价值为W i的货币O(m∑A i)将每种货币i拆成价值为W i,2W i,4W i,8W i……的货币O(m∑log A i)单调队列O(mn) ，暂时跳过背包问题——一类典型应用 给定n种货币分为k组，每组只能选一个，问能否凑出m元f[i,j,k]表示用前1~i-1组和第i组的前j个能否凑出k元。

[转载]教你彻底学会动态规划——⼊门篇动态规划相信⼤家都知道，动态规划算法也是新⼿在刚接触算法设计时很苦恼的问题，有时候觉得难以理解，但是真正理解之后，就会觉得动态规划其实并没有想象中那么难。

⽹上也有很多关于讲解动态规划的⽂章，⼤多都是叙述概念，讲解原理，让⼈觉得晦涩难懂，即使⼀时间看懂了，发现当⾃⼰做题的时候⼜会觉得⽆所适从。

我觉得，理解算法最重要的还是在于练习，只有通过⾃⼰练习，才可以更快地提升。

话不多说，接下来，下⾯我就通过⼀个例⼦来⼀步⼀步讲解动态规划是怎样使⽤的，只有知道怎样使⽤，才能更好地理解，⽽不是⼀味地对概念和原理进⾏反复琢磨。

⾸先，我们看⼀下这道题（此题⽬来源于北⼤POJ）：数字三⾓形(POJ1163)在上⾯的数字三⾓形中寻找⼀条从顶部到底边的路径，使得路径上所经过的数字之和最⼤。

路径上的每⼀步都只能往左下或右下⾛。

只需要求出这个最⼤和即可，不必给出具体路径。

三⾓形的⾏数⼤于1⼩于等于100，数字为 0 - 99输⼊格式：5 //表⽰三⾓形的⾏数接下来输⼊三⾓形73 88 1 02 7 4 44 5 2 6 5要求输出最⼤和接下来，我们来分析⼀下解题思路：⾸先，肯定得⽤⼆维数组来存放数字三⾓形然后我们⽤D( r, j) 来表⽰第r⾏第 j 个数字(r,j从1开始算)我们⽤MaxSum(r, j)表⽰从D(r,j)到底边的各条路径中，最佳路径的数字之和。

因此，此题的最终问题就变成了求 MaxSum(1,1)当我们看到这个题⽬的时候，⾸先想到的就是可以⽤简单的递归来解题：D(r, j)出发，下⼀步只能⾛D(r+1,j)或者D(r+1, j+1)。

故对于N⾏的三⾓形，我们可以写出如下的递归式：if ( r == N)MaxSum(r,j) = D(r,j)elseMaxSum( r, j) = Max{ MaxSum(r＋1,j), MaxSum(r+1,j+1) } + D(r,j)根据上⾯这个简单的递归式，我们就可以很轻松地写出完整的递归代码：#include <iostream>#include <algorithm>#define MAX 101using namespace std;int D[MAX][MAX];int n;int MaxSum(int i, int j){if(i==n)return D[i][j];int x = MaxSum(i+1,j);int y = MaxSum(i+1,j+1);return max(x,y)+D[i][j];}int main(){int i,j;cin >> n;for(i=1;i<=n;i++)for(j=1;j<=i;j++)cin >> D[i][j];cout << MaxSum(1,1) << endl;}对于如上这段递归的代码，当我提交到POJ时，会显⽰如下结果：对的，代码运⾏超时了，为什么会超时呢？答案很简单，因为我们重复计算了，当我们在进⾏递归时，计算机帮我们计算的过程如下图：就拿第三⾏数字1来说，当我们计算从第2⾏的数字3开始的MaxSum时会计算出从1开始的MaxSum，当我们计算从第⼆⾏的数字8开始的MaxSum的时候⼜会计算⼀次从1开始的MaxSum，也就是说有重复计算。

动态规划基础-----01背包（总结）1、动态规划（DP） 动态规划（Dynamic Programming，DP）与分治区别在于划分的⼦问题是有重叠的，解过程中对于重叠的部分只要求解⼀次，记录下结果，其他⼦问题直接使⽤即可，减少了重复计算过程。

另外，DP在求解⼀个问题最优解的时候，不是固定的计算合并某些⼦问题的解，⽽是根据各⼦问题的解的情况选择其中最优的。

动态规划求解具有以下的性质： 最优⼦结构性质、⼦问题重叠性质 最优⼦结构性质：最优解包含了其⼦问题的最优解，不是合并所有⼦问题的解，⽽是找最优的⼀条解线路，选择部分⼦最优解来达到最终的最优解。

⼦问题重叠性质：先计算⼦问题的解，再由⼦问题的解去构造问题的解（由于⼦问题存在重叠，把⼦问题解记录下来为下⼀步使⽤，这样就直接可以从备忘录中读取）。

其中备忘录中先记录初始状态。

2、求解思路 ①、将原问题分解为⼦问题（⼦问题和原问题形式相同，且⼦问题解求出就会被保存）； ②、确定状态：01背包中⼀个状态就是个物体中第个是否放⼊体积为背包中； ③、确定⼀些初始状态（边界状态）的值； ④、确定状态转移⽅程，如何从⼀个或多个已知状态求出另⼀个未知状态的值。

（递推型）3、01背包问题求解思路 ①、确认⼦问题和状态 01背包问题需要求解的就是，为了体积V的背包中物体总价值最⼤化，件物品中第件应该放⼊背包中吗？（其中每个物品最多只能放⼀件） 为此，我们定义⼀个⼆维数组，其中每个元素代表⼀个状态，即前个物体中若⼲个放⼊体积为背包中最⼤价值。

数组为：，其中表⽰前件中若⼲个物品放⼊体积为的背包中的最⼤价值。

②、初始状态 初始状态为和都为0，前者表⽰前0个物品（也就是空物品）⽆论装⼊多⼤的包中总价值都为0，后者表⽰体积为0的背包啥价值的物品都装不进去。

我⾃⼰写的的没保存，只能把这个整来凑数了伪代码for(int t=1;t<=n;t++){for(int j=V;j>=v[t];j--){dp[j]=max(dp[j],dp[j-v[t]]+w[t]);}}。

动态规划部分知识点总结动态规划的基本思想动态规划的基本思想可以用“递推”来描述。

在解决一个问题时，通常需要先确定一个递推关系，然后利用递推关系逐步求解问题的最优解。

以求解最长递增子序列（Longest Increasing Subsequence，LIS）问题为例，最长递增子序列是指在一个无序的序列中找到一个最长的子序列，要求子序列中的元素是递增的。

假设原序列为A，最长递增子序列的长度为LIS(i)，则可以通过递推关系来解决这个问题：LIS(i) = max(LIS(j)+1)，其中j<i 且A[j]<A[i]通过这个递推关系，我们可以逐步求解出从A[1]到A[n]的最长递增子序列的长度，最终得到整个序列的最长递增子序列。

动态规划的特点动态规划有一些特点，可以帮助我们更好地理解和应用这种方法。

1. 重叠子问题：动态规划的关键特点之一是重叠子问题，即原问题可以分解为若干个子问题，不同的子问题可能有重叠的部分。

通过记录和利用子问题的解，可以避免重复计算，提高计算效率。

2. 最优子结构：动态规划适用于具有最优子结构性质的问题。

最优子结构指的是原问题的最优解可以通过子问题的最优解来求解。

换句话说，原问题的最优解可以由子问题的最优解推导出来。

3. 状态转移方程：动态规划问题通常可以通过状态转移方程来描述。

状态转移方程是指原问题与子问题之间的关系，它可以用数学公式或递推关系来表示。

通过状态转移方程，可以确定问题的递推规律，从而求解问题的最优解。

动态规划的应用动态规划广泛应用于各种领域，比如算法设计、优化问题、数据挖掘等。

它可以解决许多经典问题，比如最短路径、背包问题、编辑距离、最长公共子序列等。

1. 最短路径：最短路径问题是指在一个加权有向图或加权无向图中，找到一条从起点到终点的路径，使得路径上的边权重之和最小。

动态规划可以用于求解最短路径问题，比如利用Floyd-Warshall算法或Dijkstra算法，通过记录并利用子问题的解来求解最短路径。

通过金矿模型介绍动态规划对于动态规划，每个刚接触的人都需要一段时间来理解，特别是第一次接触的时候总是想不通为什么这种方法可行，这篇文章就是为了帮助大家理解动态规划，并通过讲解基本的01背包问题来引导读者如何去思考动态规划。

本文力求通俗易懂，无异性，不让读者感到迷惑，引导读者去思考，所以如果你在阅读中发现有不通顺的地方，让你产生错误理解的地方，让你难得读懂的地方，请跟贴指出，谢谢！----第一节----初识动态规划--------经典的01背包问题是这样的：有一个包和n个物品，包的容量为m，每个物品都有各自的体积和价值，问当从这n个物品中选择多个物品放在包里而物品体积总数不超过包的容量m时，能够得到的最大价值是多少？[对于每个物品不可以取多次，最多只能取一次，之所以叫做01背包，0表示不取，1表示取]为了用一种生动又更形象的方式来讲解此题，我把此题用另一种方式来描述，如下:有一个国家，所有的国民都非常老实憨厚，某天他们在自己的国家发现了十座金矿，并且这十座金矿在地图上排成一条直线，国王知道这个消息后非常高兴，他希望能够把这些金子都挖出来造福国民，首先他把这些金矿按照在地图上的位置从西至东进行编号，依次为0、1、2、3、4、5、6、7、8、9，然后他命令他的手下去对每一座金矿进行勘测，以便知道挖取每一座金矿需要多少人力以及每座金矿能够挖出多少金子，然后动员国民都来挖金子。

题目补充1：挖每一座金矿需要的人数是固定的，多一个人少一个人都不行。

国王知道每个金矿各需要多少人手，金矿i需要的人数为peopleNeeded[i]。

题目补充2：每一座金矿所挖出来的金子数是固定的，当第i座金矿有peopleNeeded[i]人去挖的话，就一定能恰好挖出gold[i]个金子。

否则一个金子都挖不出来。

题目补充3：开采一座金矿的人完成开采工作后，他们不会再次去开采其它金矿，因此一个人最多只能使用一次。

题目补充4：国王在全国范围内仅招募到了10000名愿意为了国家去挖金子的人，因此这些人可能不够把所有的金子都挖出来，但是国王希望挖到的金子越多越好。