<4D F736F F F696E74202D20B5DA3230BDB25FB6AFCCACB9E6BBAE2E BBCE6C8DDC4A3CABD5D>

Size: px

Start display at page:

Download "<4D F736F F F696E74202D20B5DA3230BDB25FB6AFCCACB9E6BBAE2E BBCE6C8DDC4A3CABD5D>"

缩溥
5 years ago
Views:

1 程序设计实习 (II): 算法设计第二十讲动态规划

2 影响搜索效率的因素搜索对象 ( 枚举什么 ) 上一节课回顾搜索顺序 ( 先枚举什么, 后枚举什么 ) BFS: 广度优先 DFS: 深度优先 A*: 估价函数最小优先剪枝 ( 及早判断出不符合要求的情况 ) 3 3

3 问题提出 : 为什么要用动态规划 BFS 和 DFS: 树形递归存在冗余计算例 1:POJ 2753 Fibonacci i 数列求 Fibonacci 数列的第 n 项 int f(int n){ if(n==0 n==1) return n; return f(n-1)+f(n-2); 4

4 树形递归存在冗余计算为了除去冗余, 需要从已知条件开始计算, 并记录计算过程中的中间结果 f(5) f(4) f(3) f(3) f(2) f(2) f(1) f(2) f(1) f(1) f(0) f(1) f(0) 1 f(1) f(0) 冗余计算! 5

5 去除冗余 : int f[n+1]; f[1]=f[2]=1; int i; 树形递归存在冗余计算 for(i=3;i<=n;i++) ; f[i] = f[i-1]+f[i-2]; cout << f[n] <<endl; 用空间换时间动态规划 6

6 什么是动态规划? 动态规划是求解包含重叠子问题的最优化方法基本思想 : 将原问题分解为相似的子问题在求解的过程中通过保存子问题的解求出原问题的解 ( 注意 : 不是简单分而治之 ) 只能应用于有最优子结构的问题 ( 即局部最优解能决定全局最优解, 或问题能分解成子问题来求解解 ) 动态规划 = 记忆化搜索 7

7 动态规划是如何工作的例 2 POJ 1163 数字三角形在上面的数字三角形中寻找一条从顶部到底边的路径, 使得路径上所经过的数字之和最大路径上的每一步都只能往左下或右下走只需要求出这只需要求出这个最大和即可, 不必给出具体路径三角形的行数大于 1 小于等于 100 数字为

8 输入格式 : POJ 1163 数字三角形问题 5 // 三角形行数, 下面是三角形要求输出最大和 9

9 算法一 : 递归解题思路设 f(i, j) 为三角形上从点 (i, j) 出发向下走的最长路径, 则 f(i, j) = max(f(i+1, j), f(i+1, j+1))+d(i, j) 要输出的就是 f(0,0) 即从最上面一点出发的最长路径 10

10 解题思路 D(r, j) 表示第 r 行第 j 个数字, MaxSum(r, j) 代表从第 r 行的第 j 个数字到底边的各条路径中, 数字之和最大的那条路径的数字之和则本题是要求 MaxSum(0,0) ( 假设行编号和一行内数字编号都从 0 开始 ) 从某个 D(r, j) 出发, 显然下一步只能走 D(r+1,j) 或者 D(r+1, j+1), 所以对于 N 行的三角形 : if ( r == N-1 ) // 最底层 MaxSum(r,j) = D(N-1,j) else MaxSum(r,j) = D(r, j)+max(maxsum(r+1,j), MaxSum(r+1,j+1)); 11

11 数字三角形的递归程序 #include <iostream> using namespace std; #define MAX 101 int n, triangle[max][max]; int longestpath(int i, int j); void main(){ int i, j; cin >> n; for(i=0; i<n; i++) for(j=0; j<=i; j++) cin >> triangle[i][j]; cout << longestpath(0,0) << endl; intlongestpath(int th(i ti, intj){ if(i==n) return 0; int x = longestpath(i+1, j); int y = longestpath(i+1, j+1); if(x<y) x=y; return x+triangle[i][j]; 12 超时!!

12 为什么超时? 回答 : 重复计算如果采用递归的方法, 深度遍历每条路径, 存在大量重复计算, 则时间复杂度为 2 n, 对于 n = 100, 肯定超时 13

13 解题思路一种可能的改进思想 : 从下往上计算, 对于每一点, 只需要保留从下面来的路径中最大的路径的和即可因为在它上面的点只关心到达它的最大路径和, 不关心它从那条路径上来的问题 : 有几种解法? 从使用不同的存储开销角度分析 14

14 解法 1 如果每算出一个 MaxSum(r,j) 就保存起来, 则可以用 o(n 2 ) 时间完成计算因为三角形的数字总数是 n(n+1)/2 此时需要的存储空间是 : int D[100][100]; // 用于存储三角形中的数字 int MaxSum[100][100]; // 用于存储每个 MaxSum(r,j) MaxSum

15 #define MAX_NUM 100 int D[MAX_NUM + 10][MAX_NUM + 10]; int N; int MaxSum[MAX_NUM + 10][MAX_NUM + 10]; int main() { int ti, j; scanf("%d", & N); for( i = 1; i <= N; i ++ ) for( j = 1; j <= i; j ++ ) scanf("%d", &D[i][j]); for( j = 1; j <= N; j ++ ) MaxSum[N][j] = D[N][j]; for( i = N; i > 1; i -- ) for( j = 1; ;j < i ;j ++ ){ if( MaxSum[i][j] > MaxSum[i][j+1] ) MaxSum[i-1][j] = MaxSum[i][j] + D[i-1][j]; else MaxSum[i-1][j] = MaxSum[i][j+1] + D[i-1][j]; printf( %d, MaxSum[1][1]); return 0; 16

16 解法 2 没必要用二维 Sum 数组存储每一个 MaxSum(r,j), 只要从底层一行行向上递推那么只要一维数组 Sum[100] 即可, 即只要存储一行的 MaxSum 值就可以比解法一改进之处在于节省空间, 时间复杂度不变 17

17 #define MAX_NUM 100 int D[MAX_NUM + 10][MAX_NUM + 10]; int N; int amaxsum[max_num + 10]; int main() { int i, j; scanf("%d", & N); for( i = 1; i <= N; i ++ ) for(j=1;j<=i;j++) j j scanf("%d", &D[i][j]); for( j = 1; j <= N; j ++ ) amaxsum[j] = D[N][j]; for( i = N; i > 1; i -- ) for( j = 1; j < i; j ++ ) { if( amaxsum[j] > amaxsum[j+1] ) amaxsum[j] = amaxsum[j] + D[i-1][j]; else amaxsum[j] = amaxsum[j+1] + D[i-1][j]; printf("%d", amaxsum[1]); return 0; 18

18 解法 3 能否不用二维数组 D[100][100] 存储数字呢? 存储开销 :n sizeof(int) 思路 : 倒过来考虑前面的思路是从底往上最终算出 MaxSum(0,0) 如果从顶往下算, 最终算出每一个 MaxSum(N-1,j), 然后再取最大的 MaxSum(N-1,j), 不就是答案吗? 此时递推公式为 : if( r == 0 ) MaxSum(r,j) = D[0][0]; else MaxSum(r,j) = Max(MaxSum(r-1,j-1), MaxSum(r-1,j))+ D[r][j]; 19

19 由于两重循环形式为 : 解法 3 for( r = 0 ; r < N ; r ++) for( (j = 0 ; j < r+1 ; j ++){.. r, j 不断递增, 所以实际上不需要 D[100][100] 数组, 每次从文件里读取下一个数字即可而每一行的每个 MaxSum(r,j) 仍然都需要存储起来. 这样, 只需要一个 Sum[100] 数组 ( 注 : 只需设一个临时存储变量, 在计算 MaxSum(r,j) 后写入数组时, 暂存 MaxSum(r-1,j) 1j)) ) 20

20 解法 3 ntmp Sum i= i= i= i= i=

21 #include <stdafx.h> #define MAX_NUM 100 int N; int Sum[MAX_NUM+1]; int main() { int i, j; int ninput = 0, ntmp = 0; memset( Sum, 0, sizeof(sum)); scanf("%d", & N); scanf("%d", &Sum[0]); for( i = 1; i < N; i ++ ) { ntmp = 0; for( (j = 0; ;j < i+1; ;j ++ ){ scanf("%d", &ninput); if (Sum[j]> ntmp) { ntmp = Sum[j]; Sum[j] += ninput; else { ninput += ntmp; ntmp = Sum[j]; Sum[j] = ninput; ntmpsum = 0; for( i = 0; i < N; i ++ ) { if (Sum[i]> ntmpsum) ntmpsum = Sum[i]; 22 printf("%d", ntmpsum); return 0;

22 递归到动规的一般转化方法原来递归函数有几个参数, 就定义一个几维的数组数组的下标是递归函数参数的取值范围数组元素的值是递归函数的返回值数的返值这样就可以从边界开始, 逐步填充数组, 相当于计算递归函数值的逆过程 23

23 动规解题的一般思路 1. 将原问题分解为子问题把原问题分解为若干个子问题, 子问题经常和原问题形式相似, 有时甚至完全一样, 只不过规模变小了子问题的解一旦求出就会被保存, 所以每个子问题只需求解一次 24

24 动规解题的一般思路 2. 确定状态将和子问题相关的各个变量的一组取值, 称之为一个状态一个状态对应于一个或多个子问题所谓某个状态下的值, 就是这个状态所对应的子问题的解所有状态的集合构成问题的状态空间状态空间的大小, 与用动态规划解决问题的时间复杂度直接相关在数字三角形的例子里, 一共有 N (N+1)/2 个数字, 所以这个问题的状态空间里一共就有 N (N+1)/2 个状态在该问题里每个状态只需要经过一次, 且在每个状态上作计算所花的时间都是和 N 无关的常数 25

25 2. 确定状态动规解题的一般思路用动态规划解题, 经常碰到的情况是 : K 个整型变量能构成一个状态 ( 如数字三角形中的行号和列号这两个变量构成状态 ) 如果这 K 个整型变量的取值范围分别是 N1, N2, Nk, 那么, 我们就可以用一个 K 维的数组 array[n1] [N2] [Nk] [Nk] 来存储各个状态的值这个值未必就是一个整数或浮点数, 可能是需要一个结构才能表示的, 那么 array 就可以是一个结构数组一个状态下的值通常会是一个或多个子问题的解 26

26 3. 确定状态转移方程动规解题的一般思路定义出什么是状态, 以及在该状态下的值后, 就要找出不同的状态之间如何迁移即如何从一个或多个值已知的状态, 求出另一个状态的值状态的迁移可以用递推公式表示, 此递推公式也可被称作状态转移方程数字三角形的状态转移方程 anmaxsum r j, Dr j r N Max anmaxsum r 1 j. anmaxsum r 1 j 1 Dr j, otherwise 27

27 例题 : 最长上升子序列一个数的序列 b i, 当 b 1 < b 2 <... < b S 的时候, 我们称这个序列是上升的对于给定的一个序列 (a 1, a 2,..., a N ), 我们可以得到一些上升的子序列 (a i1, a i2,..., a ik ), 这里 1 <= i 1 < i 2 <... < i K <= N 比如, 对于序列 (1,7,3,5,9,4,8), 有它的一些上升子序列, 如 (1, 7), (3, 4, 8) 等等这些子序列中最长的长度是 4, 比如子序列 (1358) (1, 3, 5, 或 (1, 3, 4, 8) 你的任务, 就是对于给定的序列, 求出最长上升子序列的长度 28

28 输入要求例题 : 最长上升子序列输入的第一行是序列的长度 N (1 <= N <= 1000) 第二行给出序列中的 N 个整数, 这些整数的取值范围都在 0 到输出要求最长上升子序列的长度输入样例输出样例 4 29

29 解题思路 (1): 找子问题经过分析, 发现求以 a k (k=1, 2, 3 N) 为终点的最长上升子序列的长度是个好的子问题这里把一个上升子序列中最右边的那个数, 称为该子序列的终点虽然这个子问题和原问题形式上并不完全一样, 但是只要这 N 个子问题都解决了, 那么这 N 个子问题的解中, 最大的那个就是整个问题的解 30

30 解题思路 (2): 确定状态上面所述的子问题只和一个变量相关, 就是数字的位置因此序列中数的位置 k 就是状态状态 k 对应的值, 就是以 a k 做为终点的最长上升子序列的长度这个问题的状态一共有 N 个 31

31 解题思路 (3): 找出状态转移方程状态定义出来后, 转移方程就不难想了假定 MaxLen (k) 表示以 a k 做为终点的最长上升子序列的长度, 那么 : MaxLen (1) = 1 MaxLen (k) = Max { MaxLen (i):1<i < k 且 a i < a k 且 k 这个状态转移方程的意思就是,MaxLen(k) 的值, 就是在 a k 左边, 终点数值小于 a k, 且长度最大的那个上升子序列的长度再加 1 因为 a k 左边任何终点小于 a k 的子序列, 加上 a k 后就能形成一个更长的上升子序列实际实现的时候实, 可以不必编写递归函数, 因为从 MaxLen(1) 就能推算出 MaxLen(2), 有了 MaxLen(1) 和 MaxLen(2) 就能推算出 MaxLen(3) 32

32 #include <stdio.h> #include <memory.h> #define MAX_N 1000 int b[max_n + 10]; int amaxlen[max_n + 10]; main(){ int N; scanf("%d", & N); for( int i = 1;i <= N;i ++ ) scanf("%d", & b[i]); amaxlen[1] = 1; for( i = 2; i <= N; i ++ ) { // 每次求以第 i 个数为终点的最长上升子序列的长度 int ntmp = 0; // 记录满足条件的, 第 i 个数左边的上升子 // 序列的最大长度 33

33 for( int j = 1;j<i;j++){// j 察看以第 j 个数为终点的最 // 长上升子序列 if( b[i] > b[j] ) { if( ntmp < amaxlen[j] ) ntmp = amaxlen[j]; amaxlen[i] = ntmp + 1; int nmax = -1; for( i = 1; i <= N; i ++ ) if( nmax < amaxlen[i]) nmax = amaxlen[i]; printf("%d\n", nmax); amaxlen[i] 的值, 就是在 b[i] 左边, 终点数值小于 b[i] 且长度最大的那个上升子序列的长度再加 1 34

34 最长公共子序列 POJ1458 给出两个字符串, 求出这样的一个最长的公共子序列的长度最长的公共子序列 : 子序列中的每个字符都能在两个原串中找到, 而且每个字符的先后顺序和原串中的先后顺序一致 35

35 最长公共子序列 Sample Input Sample Output abcfbc abfcab 4 programming contest 2 abcd mnp 0 36

36 算法 1: 递归设两个字符串分别是 char str1[maxl]; 长度是 len1 char str2[maxl]; 长度是 len2 设 f(str1,len1,str2,len2) 为 str1 和 str2 的最大公共子串的长度, 则可以对两个字符串的最后一个字符的情况进行枚举 : 情况一 :str1[len1-1] == str2[len1-1], 则 f(str1,len1,str2,len2) = 1+ f(str1,len1-1,str2,len2-1) 1str2len21) 情况二 :str1[len1-1]!= str2[len1-1], 则 f(str1,len1,str2,len2) (f( t 1 l 1 1 t2l 2) f(t1l 1 t2l 21)) = max(f(str1,len1-1,str2,len2), f(str1,len1,str2,len2-1)) 程序如下 : 37

37 算法 1: 递归 #include <iostream> using namespace std; #include <string.h> #define MAX 1000 char str1[max], str2[max]; int commonstr(int,int); int); void main(){ while(cin>> str1 >> str2){ intlen1=strlen(str1); intlen2=strlen(str2); e cout<<commonstr(len1-1,len2-1); cout<<endl; 38

38 算法 1: 递归 int commonstr(int len1,int len2){ if(len1==-1 len2==-1) return 0; if(str1[len1]==str2[len2]) 1] t 2]) return 1+commonstr(len1-1,len2-1); else{ int tmp1=commonstr(len1-1,len2); int tmp2=commonstr(len1,len2-1); if(tmp1>tmp2) return eu tmp1; else p return tmp2; 超时! 39

39 输入两个子串 s1,s2 算法 2: 动态规划设 MaxLen(i, j) 表示 : s1 的左边 i 个字符形成的子串, 与 s2 左边的 j 个字符形成的子串的最长公共子序列的长度 MaxLen(i, a e (,j) 就是本题的状态, 定义一数组假定 len1 = strlen(s1), len2 = strlen(s2) 那么题目就是要求 MaxLen(len1,len2) len2) 40

40 显然 : 算法 2: 动态规划 MaxLen(n,0) = 0 ( n=0 len1) MaxLen(0,n) = 0 ( n=0 len2) 递推公式 : if ( s1[i-1] == s2[j-1] ) else MaxLen(i,j) (,j) = MaxLen(i-1,j-1) + 1; MaxLen(i,j) = Max(MaxLen(i,j-1), MaxLen(i-1,j)); 41

41 S1 长度为 i S1 s1[i-1] S2 长度为 j S1 i-1 S2 s2[j-1] S2 j-1 MaxLen(S1,S2) 不会比 MaxLen(S1,S2 j-1) ) 和 MaxLen(S1 i-1,s2) 都大, 也不会比两者中任何一个小 42

42 #include <iostream> #include <string.h> using namespace std; char sz1[1000]; char sz2[1000]; int anmaxlen[1000][1000]; int main(){ while( cin >> sz1 >> sz2 ) { int nlength1 = strlen( sz1); int nlength2 = strlen( sz2); int ntmp; int i, j; for( i = 0; i <= nlength1; i ++ ) anmaxlen[i][0] [][ ] = 0; for( j = 0; j <= nlength2; j ++ ) anmaxlen[0][j] = 0; 43

43 44 for( i = 1;i <= nlength1;i ++ ) { for( j = 1; j <= nlength2; j ++ ) { if( sz1[i-1] == sz2[j-1] ) anmaxlen[i][j] = anmaxlen[i-1][j-1] + 1; else { int nlen1 = anmaxlen[i][j-1]; int nlen2 = anmaxlen[i-1][j]; if( nlen1 > nlen2 ) anmaxlen[i][j] = nlen1; else anmaxlen[i][j] = nlen2; cout << anmaxlen[nlength1][nlength2] << endl;

44 例题 : POJ 1661 Help Jimmy "Help Jimmy" 是在下图所示的场景上完成的游戏 : 45

45 例题 : POJ 1661 Help Jimmy 场景中包括多个长度和高度各不相同的平台地面是最低的平台, 高度为零, 长度无限老鼠 Jimmy 在时刻 0 从高于所有平台的某处开始下落, 它的下落速度始终为 1 米 / 秒当 Jimmy 落到某个平台上时, 游戏者选择让它向左还是向右跑, 它跑动的速度也是 1 米 / 秒当 Jimmy 跑到平台的边缘时, 开始继续下落 Jimmy 每次下落的高度不能超过 MAX 米, 不然就会摔死, 游戏也会结束设计一个程序, 计算 Jimmy 到地面时可能的最早时间 46

46 输入数据第一行是测试数据的组数 t(0<=t<=20) t 每组测试数据的第一行是四个整数 N,X,Y,MAX, 用空格分隔 N 是平台的数目 ( 不包括地面 ),X X 和 Y 是 Jimmy 开始下落的位置的横竖坐标,MAX 是一次下落的最大高度接下来的 N 行每行描述一个平台, 包括三个整数,X1[i], X2[i] 和 H[i] H[i] 表示平台的高度,X1[i] 和 X2[i] 表示平台左右端点的横坐标 1 <= N <= 1000, <= X, X1[i], X2[i] <= 20000,0 < H[i] < Y <= 20000(i = 1..N) 所有坐标的单位都是米 Jimmy 的大小和平台的厚度均忽略不计如果 Jimmy 恰好落在某个平台的边缘, 被视为落在平台上所有的平台均不重叠或相连测试数据保 Jimmy 一定能安全到达地面 47

47 输出要求对输入的每组测试数据, 输出一个整数,Jimmy 到地面时可能的最早时间输入样例输出样例 23 48

48 解题思路 (1) Jimmy 跳到一块板上后, 可以有两种选择, 向左走, 或向右走走到左端和走到右端所需的时间, 是很容易计算如果我们能知道, 以左端为起点到达地面的最短时间, 和以右端为起点到达地面的最短时间, 那么向左走还是向右走, 就很容选择因此, 整个问题就被分解成两个子问题, 即 Jimmy 所在位置下方第一块板左端为起点到地面的最短时间, 和右端为起点到地面的最短时间这两个子问题在形式上和原问题是完全一致的将板子从上到下从 1 开始进行无重复的编号 ( 越高的板子编号越小, 高度相同的几块板子, 哪块编号在前无所谓 ), 那么, 和上面两个子问题相关的变量就只有板子的编号 49

49 解题思路 (2) 不妨认为 Jimmy 开始的位置是一个编号为 0, 长度为 0 的板子, 假设 LeftMinTime(k) 表示从 k 号板子左端到地面的最短时间, RightMinTime(k) 表示从 k 号板子右端到地面的最短时间, 那么, 求板子 k 左端点到地面的最短时间的方法如下 : 令 : h(i) 代表 i 号板子的高度, Lx(i) 代表 i 号板子左端点的横坐标, Rx(i) () 代表 i 号板子右端点的横坐标则 :h(k)-h(m) 当然就是从 k 号板子跳到 m 号板子所需要的时间, Lx(k)-Lx(m) 就是从 m 号板子的落脚点走到 m 号板子左端点的时间,Rx(m)-Lx(k) 就是从 m 号板子的落脚点走到右端点所需的时间 50

50 求 LeftMinTime(k) 的过程 if ( 板子 k 左端正下方没有别的板子 ){ if( 板子 k 的高度 h(k)>max) LeftMinTime(k) = ; else LeftMinTime(k) = h(k); else if( 板子 k 左端正下方的板子编号是 m ) LeftMinTime(k) = h(k)-h(m) ( ) + Min( LeftMinTime(m) + Lx(k)-Lx(m), RightMinTime(m) + Rx(m)-Lx(k) ); 求 RightMinTime(k) 的过程类似 h(k)-h(m) h(m) 51 LeftMinTime(m) Lx(k)-Lx(m) Rx(m)-Lx(k) RightMinTime(m)

51 实现考虑不妨认为 Jimmy 开始的位置是一个编号为 0, 长度为 0 的板子, 那么整个问题就是要求 LeftMinTime(0) 输入数据中, 板子并没有按高度排序, 所以程序中一定要首先将板子排序 LeftMinTime(k) () 和 RightMinTime(k) 可以用同一个过程来实现 ( 用一个布尔变量来区分 ) 具体实现参考教材 P231 52

52 53 Help Jimmy 的非递归解法 #include<iostream> using namespace std; const int inf=0x7fffffff; struct Board{ int high; int left; int right; ; Board board[1005]; int cmp(const void *a,const void *b) { // 按高度从大到小排序 return (*(Board *)b).high-(*(board *)a).high; int min(int a, int b) {return a > b? b:a; int main(){ int i, j, t, N, X, Y, MAX, ans; int f[1005][2]; bool LEFT, RIGHT; cin>>t;

53 while(t--){ cin>>n>>x>>y>>max; ans=inf; board[0].left=board[0].right=x; board[0].high=y; f[0][0]=f[0][1]=0; f[0][1] 0; for(i=1;i<=n;i++){ cin>>board[i].left>>board[i].right>>board[i].high; f[i][0]=f[i][1]=inf; f[i][1] inf; qsort(board,n+1,sizeof(board[0]), cmp); for(i=0;i<=n;i++){ if(f[i][0]==f[i][1]&&f[i][0]==inf) continue; LEFT=RIGHT=0; for(j=i+1;j<=n&&board[i].high-board[j].high<=max &&!(LEFT&&RIGHT);j++){ // 在可以掉下的范围内进行 if(board[i].left>=board[j].left&&board[i].left<=board[j].right&&!left) left&&board[i] left<=board[j] right&&!left) { // 如果左边可以掉下 f[j][0]=min(f[j][0],f[i][0]+board[i].left-board[j].left); f[j][1]=min(f[j][1],f[i][0]+board[j].right-board[i].left); f[i][0]+board[j] right-board[i] LEFT=1; 54

54 if(board[i].right>=board[j].left&&board[i].right<=board[j].right&&!right){ // 如果右边可以掉下 f[j][0]=min(f[j][0] min(f[j][0], f[i][1]+board[i].right f[i][1]+board[i]right-board[j] board[j].left); f[j][1]=min(f[j][1], f[i][1]+board[j].right-board[i].right); RIGHT=1; if(board[i].high<=max&&!left) ans=min(ans, f[i][0]); // 如果可以直接从左边掉在地上 if(board[i].high<=max&&!right) ans=min(ans, f[i][1]); // 如果可以直接从右边掉在地上 cout<<ans+y<<endl; return 0; // 类似于数字三角形问题, 可能还会有其他解法 55

55 总结 : 动规的要诀用动态规划解题, 关键是要找出状态, 和在状态间进行转移的办法 ( 即状态转移方程 ) 我们一般在动规的时候所用到的一些数组, 也就是用来存储每个状态的最优值的 56

56 小结枚举 > 搜索 > 动态规划 ( 系统化 ) ( 记忆化 ) 57

57 方式 1: 递归 - 剪枝搜索的实现整个搜索过程中, 最终状态始终不变不要考虑明显不能到达最终状态的路径方式 2: 动态规划目的在搜索过程中, 把计算的结果保留下来后面的搜索过程中, 努力使用前面搜索过程的计算机结果, 避免重复的计算方法把最终目标分解成一些相对简单的目标先实现这些相对简单的目标, 在此基础上实现最终的目标具体使用哪种方式? 依情况而定没有什么重复的计算可以使用 : 递归, 为保持简洁重复的计算占的比重很大 : 动态规划, 为提高效率 58

C++ 程序设计告别 OJ1 - 参考答案 MASTER 2019 年 5 月 3 日 1

C++ 程序设计告别 OJ1 - 参考答案 MASTER 2019 年 5 月 3 日 1 C++ 程序设计告别 OJ1 - 参考答案 MASTER 2019 年月 3 日 1 1 INPUTOUTPUT 1 InputOutput 题目描述用 cin 输入你的姓名 ( 没有空格 ) 和年龄 ( 整数 ), 并用 cout 输出输入输出符合以下范例输入 master 999 输出 I am master, 999 years old. 注意 "," 后面有一个空格,"." 结束,