《数据结构域算法设计C案例04动态规划》由会员分享，可在线阅读，更多相关《数据结构域算法设计C案例04动态规划（57页珍藏版）》请在金锄头文库上搜索。
1、2018/9/11,1,第四讲,动态规划 （Dynamic programming）,2018/9/11,2,一、经典问题：数塔问题,有形如下图所示的数塔，从顶部出发，在每一结点可以选择向左走或是向右走，一直走到底层，要求找出一条路径，使路径上的值最大。,2018/9/11,3,用暴力的方法，可以吗？,2018/9/11,4,这道题如果用枚举法（暴力思想），在数塔层数稍大的情况下（如31），则需要列举出的路径条数将是一个非常庞大的数目（230= 10243 109=10亿）。,试想一下：,2018/9/11,5,拒绝暴力，倡导和谐,2018/9/11,6,从顶点出发时到底向左走还是向右走应取决
2、于是从左走能取到最大值还是从右走能取到最大值，只要左右两道路径上的最大值求出来了才能作出决策。同样，下一层的走向又要取决于再下一层上的最大值是否已经求出才能决策。这样一层一层推下去，直到倒数第二层时就非常明了。如数字2，只要选择它下面较大值的结点19前进就可以了。所以实际求解时，可从底层开始，层层递进，最后得到最大值。结论：自顶向下的分析，自底向上的计算。,考虑一下：,2018/9/11,7,思路：从倒数第二行起， 按照状态转移方程dpij = max(dpi + 1j, dpi + 1j + 1) + valij向上递推， 直到val11， 此时dp11就是结果,2018/9/11,8,二、
3、经典问题：最长有序子序列,问题描述 找出由n个元素组成的序列的最长有序子序列长度及其中一个最长有序子序列 （注：这里有序指非递减顺序，且不要求子序列连续）。 例如，对于序列3, 7, 1, 5, 9, 3，其中最长有序子序列长度为3，这样的子序列有： 3, 7, 9、1, 5, 9、3, 5, 9。,2018/9/11,9,二、经典问题：最长有序子序列,2018/9/11,10,二、经典问题：最长有序子序列,2018/9/11,11,二、经典问题：最长有序子序列,2018/9/11,12,三 1160 FatMouses Speed,Problem Description FatMouse b
4、elieves that the fatter a mouse is, the faster it runs. To disprove this, you want to take the data on a collection of mice and put as large a subset of this data as possible into a sequence so that the weights are increasing, but the speeds are decreasing. Input Input contains data for a bunch of m
5、ice, one mouse per line, terminated by end of file. The data for a particular mouse will consist of a pair of integers: the first representing its size in grams and the second representing its speed in centimeters per second. Both integers are between 1 and 10000. The data in each test case will con
6、tain information for at most 1000 mice. Two mice may have the same weight, the same speed, or even the same weight and speed.,2018/9/11,13,三 1160 FatMouses Speed,Output Your program should output a sequence of lines of data; the first line should contain a number n; the remaining n lines should each
7、 contain a single positive integer (each one representing a mouse). If these n integers are m1, m2,., mn then it must be the case that Wm1 Sm2 . Smn In order for the answer to be correct, n should be as large as possible. All inequalities are strict: weights must be strictly increasing, and speeds m
8、ust be strictly decreasing. There may be many correct outputs for a given input, your program only needs to find one.,2018/9/11,14,三 1160 FatMouses Speed,Sample Input6008 1300 6000 2100500 2000 1000 4000 1100 3000 6000 2000 8000 1400 6000 1200 2000 1900,Sample Output 4 4 5 9 7,2018/9/11,15,三 1160 Fa
9、tMouses Speed,解题思路： 题目要求找到的体重递增，速度递减 老鼠，先把老鼠的体重进行升序排序 然后算出速度的最长递减子序列。,2018/9/11,16,四 1087 Super Jumping! Jumping! Juping!,Problem Description Nowadays, a kind of chess game called “Super Jumping! Jumping! Jumping!” is very popular in HDU. Maybe you are a good boy, and know little about this game, so
10、 I introduce it to you now. The game can be played by two or more than two players. It consists of a chessboard（棋盘）and some chessmen（棋子）, and all chessmen are marked by a positive integer or “start” or “end”. The player starts from start-point and must jumps into end-point finally. In the course of
11、jumping, the player will visit the chessmen in the path, but everyone must jumps from one chessman to another absolutely bigger (you can assume start-point is a minimum and end-point is a maximum.). And all players cannot go backwards. One jumping can go from a chessman to next, also can go across m
12、any chessmen, and even you can straightly get to end-point from start-point. Of course you get zero point in this situation. A player is a winner if and only if he can get a bigger score according to his jumping solution. Note that your score comes from the sum of value on the chessmen in you jumpin
13、g path. Your task is to output the maximum value according to the given chessmen list.,2018/9/11,17,四 1087 Super Jumping! Jumping! Juping!,Input Input contains multiple test cases. Each test case is described in a line as follow: N value_1 value_2 value_N It is guarantied that N is not more than 100
14、0 and all value_i are in the range of 32-int. A test case starting with 0 terminates the input and this test case is not to be processed. Output For each case, print the maximum according to rules, and one line one case.,2018/9/11,18,四 1087 Super Jumping! Jumping! Juping!,Sample Input 3 1 3 2 4 1 2
15、3 4 4 3 3 2 1 0Sample Output 4 10 3,解题思路？,找序列中最大升序子序列的和,2018/9/11,20,动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题,算法总体思想,2018/9/11,21,但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。,算法总体思想,2018/9/11,22,如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。,算法总体思想,T(n),2018/9/11,23,动态规划基本步骤,
16、找出最优解的性质，并刻划其结构特征。 递归地定义最优值。 以自底向上的方式计算出最优值。 根据计算最优值时得到的信息，构造最优解。,2018/9/11,24,动态规划算法的基本要素,一、最优子结构,问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。 在分析问题的最优子结构性质时，所用的方法具有普遍性：首先假设由问题的最优解导出的子问题的解不是最优的，然后再设法说明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。 利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。最优子结构是问题能用动态规划算法求解的前提。,同一个问题可以有多种方式刻划它的最优子结构，有些表示方法的求解速度更快（空间占用小，问题的维度低）,2018/9/11,25,动态规划算法的基本要素,二、重叠子问题,递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。这种性质称为子问题的重叠性质。 动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果。 通常不同的子问题个数随问题的大小呈多项式增长。因此用动态规划算法只需要多项式时间，从而获得较高的解题效率。,
