[规划求解是什么意思]什么是动态规划？动态规划的意义是什么？

[规划求解是什么意思]什么是动态规划？动态规划的意义是什么？ [规划求解是什么意思]什么是动态规划,动 态规划的意义是什么, 篇一 : 什么是动态规划,动态规划的意义是什么, 网友熊大大对[动态规划]什么是动态规划,动态规划的意义是什么,给出的答复: 动态规划中递推式的求解方法不是动态规划的本质。 我曾经作为省队成员参加过NOI，保送之后也给学校参加NOIP的同学多次讲过动态规划，我试着讲一下我理解的动态规划，争取深入浅出。希望你看了我的答案，能够喜欢上动态规划。 0. 动态规划的本质，是对问题状态的定义和状态转移方程的定义。 引自维基百科 dynamic programmingis a method for solving a complex problem by breaking it down into a collection of simpler subproblems.动态规划是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推的方式去解决。 本题下的其他答案，大多都是在说递推的求解方法，但如何拆分问题，才是动态规划的核心。 而拆分问题，靠的就是状态的定义和状态转移方程的定义。 1. 什么是状态的定义, 首先想说大家千万不要被下面的数学式吓到，这里只涉及到了函数相关的知识。 我们先来看一个动态规划的教学必备题: 给定一个数列，长度为N， 求这个数列的最长上升子数列的长度. 以 1 7 2 8 3 4 为例。 这个数列的最长递增子数列是 1 2 3 4，长度为4; 次长的长度为3， 包括 1 7 8; 1 2 3 等.要解决这个问题，我们首先要定义这个问题和这个问题的子问题。 有人可能会问了，题目都已经在这了，我们还需定义这个问题吗,需要，原因就是这个问题在字面上看，找不出子问题，而没有子问题，这个题目就没办法解决。 所以我们来重新定义这个问题: 给定一个数列，长度为N， 设为:以数列中第k项结尾的最长递增子序列的长度. 求中的最大值.显然，这个新问题与原问题等价。 而对于来讲，都是的子问题:因为以第k项结尾的最长递增子序列，包含着以第中某项结尾的LIS。 上述的新问题也可以叫做状态，定义中的“为数列中第k项结尾的LIS的长度”，就叫做对状态的定义。 之所以把做“状态”而不是“问题” ，一是因为避免跟原问题中“问题”混淆，二是因为这个新问题是数学化定义的。 对状态的定义只有一种吗,当然不是。 我们甚至可以二维的，以完全不同的视角定义这个问题: 给定一个数列，长度为N， 设为: 在前i项中的，长度为k的最长递增子序列中，最后一位的最小值. . 若在前i项中，不存在长度为k的最长递增子序列，则为正无穷. 求最大的x，使得不为正无穷。这个新定义与原问题的等价性也不难，请读者体会一下。 上述的就是状态，定义中的“为:在前i项中，长度为k的最长递增子序列中，最后一位的最小值”就是对状态的定义。 2. 什么是状态转移方程, 上述状态定义好之后，状态和状态之间的关系式，就叫做状态转移方程。 比如，对于LIS问题，我们的第一种定义: 设为:以数列中第k项结尾的最长递增子序列的长度.设A为题中数列，状态转移方程为: 用文字解释一下是: 以第k项结尾的LIS的长度是:保证第i项比第k项小的情况下，以第i项结尾的LIS长度加一的最大值，取遍i的所有值。 第二种定义: 设为:在数列前i项中，长度为k的递增子序列中，最后一位的最小值设A为题中数列，状态转移方程为: 若则 否则: 大家套着定义读一下就可以了，应该不难理解，就是有点绕。 这里可以看出，这里的状态转移方程，就是定义了问题和子问题之间的关系。 可以看出，状态转移方程就是带有条件的递推式。 3. 动态规划迷思 本题下其他用户的回答跟动态规划都有或多或少的联系，我也讲一下与本答案的联系。 a. “缓存”，“重叠子问题”，“记忆化”: 这三个名词，都是在阐述递推式求解的技巧。以Fibonacci数列为例，计算第100项的时候，需要计算第99项和98项;在计算第101项的时候，需要第100项和第99项，这时候你还需要重新计算第99项吗,不需要，你只需要在第一次计算的时候把它记下来就可以了。 上述的需要再次计算的“第99项”，就叫“重叠子问题”。如果没有计算过，就按照递推式计算，如果计算过，直接使用，就像“缓存”一样，这种方法，叫做“记忆化”，这是递推式求解的技巧。这种技巧，通俗的说叫“花费空间来节省时间”。都不是动态规划的本质，不是动态规划的核心。 b. “递归”: 递归是递推式求解的方法，连技巧都算不上。 c. “无后效性”，“最优子结构”: 上述的状态转移方程中，等式右边不会用到下标大于左边i或者k的值，这是”无后效性”的通俗上的数学定义，符合这种定义的状态定义，我们可以说它具有“最优子结构”的性质，在动态规划中我们要做 的，就是找到这种“最优子结构”。 在对状态和状态转移方程的定义过程中，满足“最优子结构”是一个隐含的条件。对状态和“最优子结构”的关系的进一步解释，什么是动态规划,动态规划的意义是什么, - 王勐的回答 写的很好，大家可以去读一下。 需要注意的是，一个问题可能有多种不同的状态定义和状态转移方程定义，存在一个有后效性的定义，不代该问题不适用动态规划。这也是其他几个答案中出现的逻辑误区: 动态规划方法要寻找符合“最优子结构“的状态和状态转移方程的定义，在找到之后，这个问题就可以以“记忆化地求解递推式”的方法来解决。而寻找到的定义，才是动态规划的本质。 有位答主说: 分治在求解每个子问题的时候，都要进行一遍计算 动态规划则存储了子问题的结果，查表时间为常数这就像说多加辣椒的菜就叫川菜，多加酱油的菜就叫鲁菜一样，是存在误解的。 文艺的说，动态规划是寻找一种对问题的观察角度，让问题能够以递推的方式去解决。寻找看问题的角度，才是动态规划中最耀眼的宝石～ 网友王勐对[动态规划]什么是动态规划,动态规划的意义是什 么,给出的答复: 动态规划的本质不在于是递推或是递归，也不需要纠结是不是内存换时间。 理解动态规划并不需要数学公式介入，只是完全解释清楚需要点篇幅…首先需要明白哪些问题不是动态规划可以解决的，才能明白为神马需要动态规划。不过好处时顺便也就搞明白了递推贪心搜索和动规之间有什么关系，以及帮助那些总是把动规当成搜索解的同学建立动规的思路。当然熟悉了之后可以直接根据问题的描述得到思路，如果有需要的话再补充吧。 动态规划是对于 某一类问题 的解决方法～～重点在于如何鉴定“某一类问题”是动态规划可解的而不是纠结解决方法是递归还是递推～ 怎么鉴定dp可解的一类问题需要从计算机是怎么工作的说起…计算机的本质是一个状态机，内存里存储的所有数据构成了当前的状态，CPU只能利用当前的状态计算出下一个状态 当你企图使用计算机解决一个问题是，其实就是在思考如何将这个问题表达成状态以及如何在状态中转移。所以所谓的空间复杂度就是为了支持你的计算所必需存储的状态最多有多少，所谓时间复杂度就 是从初始状态到达最终状态中间需要多少步～ 太抽象了还是举个例子吧: 比如说我想计算第100个非波那契数，每一个非波那契数就是这个问题的一个状态，每求一个新数字只需要之前的两个状态。所以同一个时刻，最多只需要保存两个状态，空间复杂度就是常数;每计算一个新状态所需要的时间也是常数且状态是线性递增的，所以时间复杂度也是线性的。 上面这种状态计算很直接，只需要依照固定的模式从旧状态计算出新状态就行，不需要考虑是不是需要更多的状态，也不需要选择哪些旧状态来计算新状态。对于这样的解法，我们叫递推。 非波那契那个例子过于简单，以至于让人忽视了阶段的概念，所谓阶段是指随着问题的解决，在同一个时刻可能会得到的不同状态的集合。非波那契数列中，每一步会计算得到一个新数字，所以每个阶段只有一个状态。想象另外一个问题情景，假如把你放在一个围棋棋盘上的某一点，你每一步只能走一格，因为你可以东南西北随便走，所以你当你同样走四步可能会处于很多个不同的位置。从头开始走了几步就是第几个阶段，走了n步可能处于的位置称为一个状态，走了这n步所有可能到达的位置的集合就是这个阶段下所有可能的状态。 现在问题来了，有了阶段之后，计算新状态可能会遇到各种奇葩的情况，针对不同的情况，就需要不同的算法，下面就分情况来说明一下: 假如问题有n个阶段，每个阶段都有多个状态，不同阶段的状态数不必相同，一个阶段的一个状态可以得到下个阶段的所有状态中的几个。那我们要计算出最终阶段的状态数自然要经历之前每个阶段的某些状态。 好消息是，有时候我们并不需要真的计算所有状态，比如这样一个弱智的棋盘问题:从棋盘的左上角到达右下角最短需要几步。答案很显然，用这样一个弱智的问题是为了帮助我们理解阶段和状态。某个阶段确实可以有多个状态，正如这个问题中走n步可以走到很多位置一样。但是同样n步中，有哪些位置可以让我们在第n+1步中走的最远呢,没错，正是第n步中走的最远的位置。换成一句熟悉话叫做“下一步最优是从当前最优得到的”。所以为了计算最终的最优值，只需要存储每一步的最优值即可，解决符合这种性质的问题的算法就叫贪心。如果只看最优状态之间的计算过程是不是和非波那契数列的计算很像,所以计算的方法是递推。 既然问题都是可以划分成阶段和状态的。这样一来我们一下子解决了一大类问题:一个阶段的最优可以由前一个阶段的最优得到。 如果一个阶段的最优无法用前一个阶段的最优得到呢, 什么你说只需要之前两个阶段就可以得到当前最优,那跟只用之前一个阶段并没有本质区别。最麻烦的情况在于你需要之前所有的情况才行。 再来一个迷宫的例子。在计算从起点到终点的最短路线时，你不能只保存当前阶段的状态，因为题目要求你最短，所以你必须知道之前走过的所有位置。因为即便你当前再的位置不变，之前的路线不同会影响你的之后走的路线。这时你需要保存的是之前每个阶段所经历的那个状态，根据这些信息才能计算出下一个状态～ 每个阶段的状态或许不多，但是每个状态都可以转移到下一阶段的多个状态，所以解的复杂度就是指数的，因此时间复杂度也是指数的。哦哦，刚刚提到的之前的路线会影响到下一步的选择，这个令人不开心的情况就叫做有后效性。 刚刚的情况实在太普遍，解决方法实在太暴力，有没有哪些情况可以避免如此的暴力呢, 契机就在于后效性。 有一类问题，看似需要之前所有的状态，其实不用。不妨也是拿最长上升子序列的例子来说明为什么他不必需要暴力搜索，进而引出动态规划的思路。 假装我们年幼无知想用搜索去寻找最长上升子序列。怎么搜索呢,需要从头到尾依次枚举是否选择当前的数字，每选定一个数字就要去看看是不是满足“上升”的性质，这里第i个阶段就是去思考是否要选择第i个数，第i个阶段有两个状态，分别是选和不选。哈哈，依稀出现了刚刚迷宫找路的影子～咦慢着，每次当我决定要选择当前数字的时候，只需要和之前选定的一个数字比较就行了～这是和之前迷宫问题的本质不同～这就可以纵容我们不需要记录之前所有的状态啊～既然我们的选择已经不受之前状态的组合的影响了，那时间复杂度自然也不是指数的了啊～虽然我们不在乎某序列之前都是什么元素，但我们还是需要这个序列的长度的。所以我们只需要记录以某个元素结尾的LIS长度就好～因此第i个阶段的最优解只是由前i-1个阶段的最优解得到的，然后就得到了DP方程 所以一个问题是该用递推、贪心、搜索还是动态规划，完全是由这 个问题本身阶段间状态的转移方式决定的～ 每个阶段只有一个状态->递推; 每个阶段的最优状态都是由上一个阶段的最优状态得到的->贪心; 每个阶段的最优状态是由之前所有阶段的状态的组合得到的->搜索; 每个阶段的最优状态可以从之前某个阶段的某个或某些状态直接得到而不管之前这个状态是如何得到的->动态规划。 每个阶段的最优状态可以从之前某个阶段的某个或某些状态直接得到这个性质叫做最优子结构; 而不管之前这个状态是如何得到的 这个性质叫做无后效性。 另:其实动态规划中的最优状态的说法容易产生误导，以为只需要计算最优状态就好，LIS问题确实如此，转移时只用到了每个阶段“选”的状态。但实际上有的问题往往需要对每个阶段的所有状态都算出一个最优值，然后根据这些最优值再来找最优状态。比如背包问题就需要对前i个包容量为j时计算出最大价值。然后在最后一个阶段中的所有状态种找到最优值。 网友蒙面大侠对[动态规划]什么是动态规划,动态规划的意义 是什么,给出的答复: 我想，大家对动态规划的困惑在于拿到一道题目，告诉你是动态规划，能很好的写出来;但自己独立分析问题特征，却很难判断出这道题目需要用动态规划来求解。 所以，冒昧的揣测一下，TZ疑惑的不是动态规划是什么，而是为何需要使用动态规划DP来求解问题。 1) 先来回到第一个问题，“动态规划是什么”, 上面的答案基本上已经说的很好了:动态规划是递归，是缓存，是用空间来换取时间;但是，如果仅仅知道这些，你还是发现无法设计动态规划的算法。因为你慢慢会发现，有些问题用动态规划和递归都能求解，但是动态规划的速度会更慢。于是有人说了，动态规划题目的特征在于最优子结构和重叠子问题——这就涉及到下一个问题 2)为什么需要使用动态规划, 在初等算法中，算法设计的思路一般如下，首先尝试穷举法;然而如何穷举, 此时往往要用到分治法——而归递，在绝大多数时候仅仅是分治法 的一种表现形式而已; 在递归和分治法的基础上，往往会用动态规划来优化——动态规划，实际上是一种升级版的分治法。 当然，不是所有的穷举都能使用分治法;不是所有的分治法都能优化成动态规划。此时，就是上文提到的:只有一个问题是可分的，才可以使用分治法;只有分治出来的子问题有重叠，才可以使用DP;只有子问题具有最优子结构，DP才具有意义。 当然，其中最难的部分可能在于对于一个没有经验的程序设计者来说，判断重叠子问题和最优子结构是不容易的，这部分就不是用文字能够使人明白的了。需要结合实例，分析才行: 动态规划分析——如何设计和实现动态规划算法 网友匿名用户对[动态规划]什么是动态规划,动态规划的意义是什么,给出的答复: 今天在网上看了一篇博文，个人感觉很不错: 动态规划 网友蒙面大侠对[动态规划]什么是动态规划,动态规划的意义是什么,给出的答复: 搞过ACM的水货答一下。 排名第一的答案本身已足够好了，但还是太过专业，不能传教于大 众，故试着来个通俗的答案。 首先，动态规划是一种算法。那么，何谓算法,计算机书籍中不难找到其严谨的学术定义，大众可以简单理解为“解决某一类问题的核心思想”。 先谈动态规划的意义——望文生义，“动态”规划对应“动态”的问题:你并不知道问题的规模会有多大，而不论是个位数还是百万级，都能以较快速度将结果正确计算出来。这是对于计算机科学最直观的意义，当然我认为其对人生亦有一定指导意义，但那是见仁见智的事了。 动态规划这一思想的实质其实是以下两点: 1.分析问题，构造状态转移方程 2.以空间换时间 让我们结合一个简单例子来理解一下: 以乘法计算为例，乘法的定义其实是做n次加法，请先忘掉九九乘法表，让你计算9*9，如何得到81这个解,计算9*10呢,9*999……以及9*n呢, 1.分析问题，构造状态转移方程 “状态转移方程”的学术定义亦可简单找到，略去不表。光看“方程”二字，可以明白它是一个式子。 针对以上问题，我们构造它的状态转移方程。 问题规模小的时候，我们可以容易得到以下式子: 9*0=0; 9*1=0+9; 9*2=0+9+9; …… 可以得到:9*n=0+9+...+9。严谨的证明可以使用数学归纳法，略去不表。 现在，定义dp=9*n,改写以上式子: dp=9*0=0; dp=9*1=dp+9; dp=9*2=dp+9; …… 作差易得:dp=dp+9;这就是状态转移方程了。 可以看到，有了状态转移方程，我们现在可以顺利求解9*n这一问题。 2.以空间换时间 虽然能解，但当n很大时，计算耗时过大，看不出状态转移方程dp=dp+9与普通方程9*n=0+9+...+9相比没有任何优势。 这时，如果dp的结果已知，dp=dp+9只需计算一次加法，而9*n=0+9+...+9则需计算n-1次加法，效率差异一望即知。 存储计算结果，可令状态转移方程加速，而对普通方程没有意义。 以空间换时间，是令动态规划具有实用价值的必备举措。 网友hancy对[动态规划]什么是动态规划,动态规划的意义是什么,给出的答复: @熊大大 的回答真好，理解的准确又深刻。 我的答案无法给出更深刻的视角，试试看看能不能在其他方面创造一点价值。 首先，看完这篇回答你会弄清楚这么几个事实: 1. 动态规划是解决问题的一种方法。 2. 动态规划的本质在于它看待问题的角度，即它试图将问题定义成这样的形式:原问题的解如何由子问题的解组合而成。一旦得到这种形式的问题定义，动态规划是有一套成熟的实现方式的。 3. 动态规划的实现方法有两大类:“自顶向下”的实现方式和“自低向上”的实现方式。其中递归属于自顶向下的实现方式。至于人们长提起的Caching所在的层次还要更低一点，它是自顶向下实现方式或者自低向上实现方式中用到的一种优化方法 好啦，下面是更详细附带栗子和饮料的长答案: 1. 动态规划是解决问题的一种方法。 是的，它只是问题的一种解决方法。一个问题完全可能同时适用多种解决方法。 2. 动态规划的本质是它试图将问题定义成这样的形式:原问题的解如何由子问题的解组合而成。如何无法将问题定义成这样的形式，那么很抱歉说明这个问题无法以动态规划求解。 我们常常说的状态转移方程，其实就是这句话的数学表达——“原问题的解如何由子问题的解组合而成”。所以 @熊大大 说“动态规划的本质，是对问题状态的定义和状态转移方程的定义。”是完全严谨准确的。 3. 对于有经验的人来说，得到了状态转移方程，该问题就已经解决了。 因为动态规划的实现就“自顶向下” 和 “自低向上” 两种。 其中递归属于“自顶向下”的实现方法，而caching则只不过是为了提升效率采用的优化方法。 4. “自顶向下”的实现方式 和 “自低向上”的实现方式各有什么优缺点，我的理解如下。 两种方法的取舍我个人的喜好是——优先选择Top-Down dynamic programming，除非不容易得到递归公式或空间复杂度无法接受。 “自顶向下”: 1.能方便的得到递归公式，并用递归函数实现 2.保持了递归实现的代码结构，逻辑上容易理解。 3.过程中只计算需要计算的子结果。 4.当采用了caching技术时多次被调用时天然的复用之前被调用时的子结果。 “自低向上”: 1.需要设计数据结构来完成自底向上的计算过程。逻辑上相对不那么直观。 2.常常可以进行空间复杂度的优化。比如Fibonacci数列可以优化为只使用两个变量的额外存储空间，0-1背包问题可以优化为O的空间复杂度。 3.若进行了空间优化，则连续多次被调用时无法复用之前被调用的子结果。 最后，如果想要更全面完整的理解动态规划，我的学习路线上只有两步: 1. 读一下Algrithm in C这本书的相应章节 2. 把几个经典动态规划问题分别用“自顶向下”和“自低向上”两种方法实现一遍，用任何你喜欢的语言都行 :)祝开心 网友Coldwings对[动态规划]什么是动态规划,动态规划的意 义是什么,给出的答复: 首先明确:动态规划是用来求解最优化问题的一种方法。常规算法书上强调的是无后效性和最优子结构描述，这套理论是正确的，但是适用与否与你的状态表述有关。至于划分阶段什么的就有些扯淡了:动态规划不一定有所谓的阶段。其实质是状态空间的状态转移。 下面的理解为我个人十年竞赛之总结。基本上在oi和acm中我没有因为动态规划而失手过。 所有的决策类求最优解的问题都是在状态空间内找一个可以到达的最佳状态。搜索的方式是去遍历每一个点，而动态规划则是把状态空间变形，由此变成从初始到目标状态的最短路问题。 依照这种描述:假若你的问题的结论包含若干决策，则可以认为从初始状态到解中间的决策流程是一个决策状态空间中的转移路线。前提是:你的状态描述可以完整且唯一地覆盖所有有效的状态空间中的点，且转移路线包含所有可能的路径。 这个描述是包含动态规划两大条件的。所谓无后效性，指状态间的转移与如何到达某状态无关。如果有关，意味着你的状态描述不能完整而唯一地包括每一个状态。如果你发现一个状态转移有后效性，很 简单，把会引起后效性的参数作为状态描述的一部分放进去将其区分开来就可以了;最优子结构说明转移路线包含了所有可能的路径，如果不具备最优子结构，意味着有部分情况没有在转移中充分体现，增加转移的描述就可以了。最终所有的搜索问题都可以描述成状态空间内的状态转移方程，只是有可能状态数量是指数阶的，有可能不满足计算要求罢了。 这样的描述下，所有的动态规划问题都可以转变为状态空间内大量可行状态点和有效转移构成的图的从初始状态到最终状态的最短路问题。 于是乎，对于动态规划，他的本质就是图论中的最短路;阶段可以去除，因为不一定有明确的阶段划分。 网友王星泽对[动态规划]什么是动态规划,动态规划的意义是什么,给出的答复: 开一个有可能得罪所有人的玩笑:据说一个答案如果文科生看不懂，那一定不是一个好答案。 目前的答案其实已经很好了，只不过还是没有深入到最深刻的本质。动态规划的最根本的本质非常简单，而且不局限于计算机算法领域。 动态规划是一种思维方法，整个学科的基本思想就是一条，动态规划之父Bellman的Principle of Optimality : 设想你想要采用最优的策略解决某件事，而且这件事可以分成好多步;假设你已经知道了做这件事的整体上最优的策略;再假设你根据这个整体最优策略走了几步，接下来剩下的几步的你重新算了一个最优子策略，如果和整体最优策略在接下来这几步的子策略相符合，那么这件事符合最优化原理;然后就可以使用动态规划的算法解决，解决思路就是一步步找出这些最优的子策略，最后得到整体最优策略。 举个例子:我想走最短的距离开车从三藩去纽约。用地图软件一查得到了下图的路径，这就是上面说的整体最优策略。我现在根据这个整体最优的路径从三藩开了两天到了芝加哥，然后我重新用地图软件查从芝加哥到纽约的最短路径，发现和之前查到的完全重合～ 这就是一个符合最优化原理、从而可以被动态规划解决的问题。 怎么解决呢,假设我们没有这个强大的地图软件，而人工地使用动态规划算法，那么步骤可以是这样的:假设所有的路径必须经过某些驿站，首先我找到从三藩出发到每一个第一站驿站的路径和距离，接 下来计算从三藩出发到每一个第二站驿站的最短路径，然后计算第三站、第四站、最后终于算到纽约，我就知道了从三藩出发到纽约的最短路径，于是就可以按照这个最短路径多快好省地出发了。。。 如果关于上面这些话，你能说服自己，那么恭喜你，你已经理解了动态规划的灵魂。。。 动态规划的理论意义也只有一个，就是最优化，哪怕你要解决的问题是随机和/或混乱的。理论上虽然动态规划可以解决符合最优化原理的问题，实际上由于curse of dimensionality等原因有很大的局限性。 最后为了不至于太过轻佻，说明一下:严格理解动态规划需要学习测度论，以上试图把动态规划这个优美的思想用最容易理解的方式表达。 网友蒙面大侠对[动态规划]什么是动态规划,动态规划的意义是什么,给出的答复: 1.只保证最终结果一致，可以减少很多搜索。 这是动态规划省时间的根本原因。 2.状态转移方程的实质也是跟1共通的。 什么情况不适合动态规划,除了最优解外还需要提供最优解的全 部分支解的。 网友鹌鹑对[动态规划]什么是动态规划,动态规划的意义是什么,给出的答复: 动态规划本质上就是高端大气上档次的贪心算法嘛。 网友Belleve对[动态规划]什么是动态规划,动态规划的意义是什么,给出的答复: 递归 + 缓存 比如，DAG 上的最短路径可以用递归定义: 而且 sp 函数引用透明，因此可以用缓存来避免重复计算。 网友王东岳对[动态规划]什么是动态规划,动态规划的意义是什么,给出的答复: 动态规划主要有两个要点 状态和转移 满足无后效性要求，基本就可以完成一个动态规划了 网友邑封对[动态规划]什么是动态规划,动态规划的意义是什么,给出的答复: 猿爸爸把 1+1+1+1+1+1+1+1 = 写在纸上，问小猿: 「它们加起来是多少哇,」 「8 ～」 猿爸爸在左边又加了个 1+，再问一次小猿: 「现在呢,」 「9 ～」 「为什么小猿这么快就知道了呢,」 「因为你刚刚加了 1 啊~」 「所以只要记得之前的结果，就不用再计一次数啦。」 嗯，动态规划就是一种「先记住些事，方便后面节约时间」的神奇方法。 -------------------------------------------------------------------------- 但是如果你觉得这个答案对你的胃口，那么恭喜你，你对 DP 的理解成功地达到了四岁小孩的水平……FYI: How should I explain dynamic programming to a 4-year-old? 不谢 网友李陶冶对[动态规划]什么是动态规划,动态规划的意义是什么,给出的答复: 我在思考这个问题的意义，这里面有个残酷的事实。 很多人在学习的时候都希望先了解整个知识结构，再去研究具体的问题。但把这种方法套用在DP上，会发现行不通。因为DP的概念比DP的问题更难理解。能在这里解释DP概念的，往往都解决了几十个或上百个DP的问题。 如果lz的提问是为了学习DP的话，我建议你先去找些DP的问题来解决，比如:动态规划的问题，从简单到难，做完第1页应该就能自己总结出个梗概了。 网友看雪对[动态规划]什么是动态规划,动态规划的意义是什么,给出的答复: 子结构有重合,用空间或者叫做缓存对其结果进行保存,空间换取时间 网友Earthson Lu对[动态规划]什么是动态规划,动态规划的意义是什么,给出的答复: 动态规划只是一个优化而已，它是通过保存那些已经求过值的状态来做到的。 很多人提到局部最优结构，但这其实不是必须的。实际情况是只要你的状态重叠足够多，重复对状态求值的代价足够高，你就应该考虑对状态做cache。讽刺的是，动态规划就是指这个cache的过程。基 本没太多技术含量，因为问题的根本在于状态怎么转移。而我们之所以尝试分析最优子结构，也是为了找到一个好的状态表示。 网友Sancha Su对[动态规划]什么是动态规划,动态规划的意义是什么,给出的答复: 计算机中常用的一种算法，核心思想是花费空间来节省时间。 将以前计算过的信息保存起来，以后计算的问题如果出现递归子问题，刚好保存过就能用。 书面点说满足动态规划是两个点，最优子结构性和无后效性。 ---其实在icpc生涯中我非常喜欢动态规划，我用白话再说说我对它的理解，请赐教--- 先举个简单的例子，可能例子不太好。 现在有N个有大小不一的球，编号为1-N，我们按顺序对球进行选择，可以选，可以不选，这样得到一个操作序列。 比如3个球，123，取球的序列有空集，1，2，3，12，13，23，123。 先不用组合数学做... 在我的理解里，搜索其实就是一种特殊的动态规划，虽然效率很搓。 定义状态status为已经选的球的集合，状态转移为选下一个球，f[n][status]为前n个球，状态status的个数 f[n][ ] = f[n - 1][ ] f[n][ ] = f[n - 1][ ] 公式不太会画，大概意思是，当前状态最大的球的编号为idn-1，那么在下一个要取的球中，那么会达到新的状态 ， 否则就是原来的状态。 结果是f[ n ][ * ] 这里可以把第一维去掉，这样的话状态的表示也满足无后效性，这其实真的是搜索，把整个球的集合都表示出来，还有什么好说的... 开始对解决的方法优化。 在转移的时候，其实质需要知道当前最大的球是什么。如果按一定的枚举顺序，状态这么表示也不会有后效。 设f[ i ] 为当前集合最大的球的编号是 i， 选择的方法个数。 非常容易发现发成就是这样，f[ i ] += f[ j ] 结果是sum 当然解法不止一个。 有一种类似背包问题的状态表示方法， f[ i ]为前i个球可能选的方法总数，转移的话更加简单，取，或者不取。 f[ i ] = f[ i - 1] * 2 结果是f[ n ] 以上的例子按我的理解都是动态规划， 1、都用状态把问题的子问题表示出来了，不一定是全局唯一的状态，至少是当前唯一的状态。 2、对于不同的状态，状态的转移符合题目的操作。 想到什么再写吧... 网友马拉轰对[动态规划]什么是动态规划,动态规划的意义是什么,给出的答复: 我只想说人家Dimitri Bertsekas两卷大书被诸位说的这么trivial是对的吗, 网友bama ao对[动态规划]什么是动态规划,动态规划的意义是什么,给出的答复: 无后效性 网友蒙面大侠对[动态规划]什么是动态规划,动态规划的意义是什么,给出的答复: 动态规划，说得白话一点就是递推。 动态规划的最终目标是解决某问题，为此，我们先解决一系列类似的问题，最终解决整个问题，而其中类似问题的解决也是用动态规划的，思想上类似第二归纳法。或者，最终目标是解决一系列类似的问题，为此，我们将其排序，某些先前解决的问题可以帮助解决后 续的问题。 另外，动态规划可以看作是贪心算法的一种，几种观点: 1、它的“当前看起来最优的”由于具有最优子结构，所以就是最优的; 2、最终解决的某问题不一定用到先前的每个情况，它的是从每个最优中选择了最优。 不知道表达得是否清楚，总的来说，动态规划还可以说是一种“目光长远”的贪心算法。 事实上下面的算法也可以算是动态规划: unsigned fib { return n 只不过，经常我们需要记录之前已经解决的问题的答案，来加速计算，这是因为一般的动态规划问题可能多次解决某个相同问题，例如上述代码中若要计算 fib，则会计算 2 次 fib，如果我们第一次求解出 fib 之后记下来，就不用每次都重新求解了。 在 OI 界，我们常常这样称呼下面的三类代码: // 暴力/递归 unsigned fib { return n // 记忆化/记忆化暴力 unsigned table[SZ]; // initialized to -1u unsigned fib { return table[n] == -1u ? n // 传统的递推/动态规划 unsigned fib[SZ]; fib[0] = 0; fib[1] = 1; for fib[i] = fib[i - 1] + fib[i - 2]; // 刷新式的动态规划 unsigned fib[SZ]; fib[0] = 0; fib[1] = 1; for fib[i + 1] = fib[i] + fib[i - 1]; // 滚动的递推/动态规划 // 注:在实践中我们常常利用模的办法进行滚动，而不是循环肤质 unsigned fm2 = 0, fm1 = 1, f; for { f = fm1 + fm2; fm2 = fm1; fm1 = f; } 另外用比较初等的说法解释一下动态规划中的术语: 阶段:每次解决一个大问题，叫做一个阶段。 状态:同一阶段里面的几个小问题，通常按照一定顺序出现。 决策:从之前的状态变换为新的状态的方式。 通常见到的是单阶段动态规划问题。 例如求解 Fibonacci 数列第 n 项的动态规划写法，它只有一个阶段，求解第 n 项结束时，第一阶段就完成了。 Fibonacci 数列的每一项就是一个状态。 利用前两项求出 Fibonacci 数列的下一项就是“决策”。在更高级的问题中“决策”涉及到更多的状态，且是这些状态“更复杂”的函数。 —————————— 被老妈催睡，OI 选手考虑高考后再完善答案。 篇二 : 河道规划中的“防洪通道”怎么解释,,有什么要求之类……, 防洪通道 河道规划中的“防洪通道”怎么解释,,有什么规范要求之类……, 河道规划中的防洪通道是为暴雨季节汛期设留的泄洪通道。只要求能满足当地汛期的泄洪即可。要求保持通道的畅通。