devbox
weixin_40725706
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

记忆化搜索_记忆化搜索时间复杂度

作者：weixin_40725706 | 2024-08-18 19:04:32

赞

踩

记忆化搜索时间复杂度

目录

 

A - Function Run Fun

B - 滑雪

C - 漫步校园

D - Free Candies

E - Zipper

F - Bone Collector

A - Function Run Fun

 POJ - 1579 

We all love recursion! Don't we?

Consider a three-parameter recursive function w(a, b, c):

if a <= 0 or b <= 0 or c <= 0, then w(a, b, c) returns:
1

if a > 20 or b > 20 or c > 20, then w(a, b, c) returns:
w(20, 20, 20)

if a < b and b < c, then w(a, b, c) returns:
w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)

otherwise it returns:
w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1)

This is an easy function to implement. The problem is, if implemented directly, for moderate values of a, b and c (for example, a = 15, b = 15, c = 15), the program takes hours to run because of the massive recursion.

Input

The input for your program will be a series of integer triples, one per line, until the end-of-file flag of -1 -1 -1. Using the above technique, you are to calculate w(a, b, c) efficiently and print the result.

Output

Print the value for w(a,b,c) for each triple.

Sample Input

  1. 1 1 1
  2. 2 2 2
  3. 10 4 6
  4. 50 50 50
  5. -1 7 18
  6. -1 -1 -1

Sample Output

  1. w(1, 1, 1) = 2
  2. w(2, 2, 2) = 4
  3. w(10, 4, 6) = 523
  4. w(50, 50, 50) = 1048576
  5. w(-1, 7, 18) = 1

思路：按照体中给出的递归方法，时间复杂度应该在o(3^n)到o(4^n)之间，但如果将每个节点的值保存下来时间复杂度就可以降到n^3，也就是所谓的记忆化搜索。

题中写法：

  1. #include<iostream>
  2. #include<algorithm>
  3. #include<set>
  4. #include<vector>
  5. #define ll long long
  6.  
  7. using namespace std;
  8.  
  9. int w(int a, int b, int c)
  10. {	
  11. 	if(a <=0 || b <= 0 || c <= 0) return 1;	
  12. 	
  13. 	if(a > 20 || b > 20 || c > 20) return w(20,20,20);	
  14. 			
  15. 	if(a < b && b < c) return w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c);
  16. 	
  17. 	return w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1);
  18. } 
  19.  
  20. int main()
  21. {
  22. 	int a,b,c;
  23. 	while(cin>>a>>b>>c)
  24. 	{
  25. 		if(a == -1 && b == -1 && c == -1) break;
  26. 		printf("w(%d, %d, %d) = %d\n",a,b,c,w(a,b,c));
  27. 	}
  28. 	return 0;
  29. }

记忆化搜索写法：

  1. #include<iostream>
  2. #include<algorithm>
  3. #include<set>
  4. #include<vector>
  5. #define ll long long
  6.  
  7. using namespace std;
  8.  
  9. int dp[100][100][100];
  10.  
  11. int w(int a, int b, int c)
  12. {	
  13. 	if(a <=0 || b <= 0 || c <= 0) return 1;	
  14. 	
  15. 	if(a > 20 || b > 20 || c > 20) return dp[a][b][c] = w(20,20,20);
  16. 	
  17. 	if(dp[a][b][c]) return dp[a][b][c];
  18. 			
  19. 	if(a < b && b < c) return dp[a][b][c] = w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c);
  20. 	
  21. 	return dp[a][b][c] = w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1);
  22. } 
  23.  
  24. int main()
  25. {
  26. 	int a,b,c;
  27. 	while(cin>>a>>b>>c)
  28. 	{
  29. 		if(a == -1 && b == -1 && c == -1) break;
  30. 		printf("w(%d, %d, %d) = %d\n",a,b,c,w(a,b,c));
  31. 	}
  32. 	return 0;
  33. }

B - 滑雪

 POJ - 1088 

Glory非常喜欢玩滑滑梯游戏，下面给出了一个n,m的滑道，其中的数字表示滑道的高度。Glory可以从一个点出发向下滑行，每次只能滑行到相邻的位置(上下左右)中高度严格低于当前高度的地方，不能重复划行已经滑行过的地方，但他希望在这个滑道上滑行尽量远的距离，也即是找一条最长的滑道。

Input

第一行输入两个数n,m代表滑梯范围行n和列m(1 <= n,m <= 100)。下面是n行，每行有m个整数，代表高度h，(0<=h<=20000)

Output

输出一个值，代表Glory能够在滑滑梯上面滑行的最长长度是多少

Sample Input

3 3
9 1 2
5 6 7
8 4 3

Sample Output

4

Sample Input

4 7
7 6 5 4 3 2 1
1 5 1 1 1 1 1
1 4 3 1 1 1 1
1 5 6 7 8 1 1

Sample Output

7

hint

样例1：7->6->4->3 长度为4

  1. #include<iostream>
  2.  
  3. using namespace std;
  4.  
  5. const int N = 330;
  6.  
  7. int dp[N][N];
  8. int r,c;
  9. int high[N][N];
  10.  
  11. int mov[4][2] = {0,1,0,-1,1,0,-1,0};
  12.  
  13. int dfs(int x, int y)
  14. {
  15.     if(dp[x][y]) return dp[x][y];
  16.     dp[x][y] = 1;
  17.     for(int i=0; i<4; i++)
  18.     {
  19.         int nx = x + mov[i][0];
  20.         int ny = y + mov[i][1];
  21.         if(nx >=1 && nx <=r && ny >=1 && ny <=c && high[x][y] > high[nx][ny]) 
  22.         {
  23.             dp[x][y] = max(dp[x][y], 1+dfs(nx,ny));
  24.         }
  25.     }
  26.     return dp[x][y];
  27. }
  28.  
  29. int main()
  30. {
  31.     cin>>r>>c;
  32.     for(int i=1; i<=r; i++)
  33.         for(int j=1; j<=c; j++)
  34.             cin>>high[i][j];
  35.             
  36.     for(int i=1; i<=r; i++)
  37.         for(int j=1; j<=c; j++)
  38.             dp[i][j] = dfs(i,j);
  39.             
  40.     int ans = 0;
  41.     for(int i=1; i<=r; i++)
  42.         for(int j=1; j<=c; j++)
  43.             ans = max(dp[i][j],ans);
  44.     cout<<ans;
  45.     return 0;
  46. }

C - 漫步校园

 HDU - 1428 

LL最近沉迷于AC不能自拔，每天寝室、机房两点一线。由于长时间坐在电脑边，缺乏运动。他决定充分利用每次从寝室到机房的时间，在校园里散散步。整个HDU校园呈方形布局，可划分为n*n个小方格，代表各个区域。例如LL居住的18号宿舍位于校园的西北角，即方格(1,1)代表的地方，而机房所在的第三实验楼处于东南端的(n,n)。因有多条路线可以选择，LL希望每次的散步路线都不一样。另外，他考虑从A区域到B区域仅当存在一条从B到机房的路线比任何一条从A到机房的路线更近(否则可能永远都到不了机房了…)。现在他想知道的是，所有满足要求的路线一共有多少条。你能告诉他吗?

Input

每组测试数据的第一行为n(2=<n<=50)，接下来的n行每行有n个数，代表经过每个区域所花的时间t(0<t<=50)(由于寝室与机房均在三楼，故起点与终点也得费时)。

Output

针对每组测试数据，输出总的路线数(小于2^63)。

Sample Input

  1. 3
  2. 1 2 3
  3. 1 2 3
  4. 1 2 3
  5. 3
  6. 1 1 1
  7. 1 1 1
  8. 1 1 1

Sample Output

  1. 1
  2. 6

思路：这题翻译成人话就是求(1,1)到(n,n)的路径有多少条，对路径的要求是从A区域走到B区域时，B区域到终点的距离要小于A区域。首先求出每点到终点的最短路径距离，再求出符合题目要求的路径数量。

  1. #include<iostream>
  2. #include<queue>
  3. #include<cstring>
  4. #define ll long long
  5.  
  6. using namespace std;
  7.  
  8. const int N = 55;
  9.  
  10. int t[N][N];
  11. ll dp[N][N];
  12. int dis[N][N];
  13. int n;
  14.  
  15. struct node{
  16. 	int x;
  17. 	int y;
  18. };
  19.  
  20. int mov[4][2] = {0,1,0,-1,1,0,-1,0};
  21.  
  22. void bfs()
  23. {
  24. 	queue<node> q;
  25. 	q.push({n,n});
  26. 	dis[n][n] = t[n][n];//当前只知道终点到终点的距离。 
  27. 	while(!q.empty())
  28. 	{
  29. 		node a = q.front();
  30. 		q.pop();
  31. 		int x = a.x;
  32. 		int y = a.y;
  33. 		for(int i=0; i<4; i++)
  34. 		{
  35. 			int nx = x + mov[i][0];
  36. 			int ny = y + mov[i][1];
  37. 			if(nx < 1 || nx > n || ny < 1 || ny > n) continue;
  38. 			if(dis[nx][ny] > dis[x][y] + t[nx][ny] || dis[nx][ny] == 0)
  39. 			{
  40. 				dis[nx][ny] = dis[x][y] + t[nx][ny];
  41. 				q.push({nx,ny});
  42. 			}
  43. 		} 
  44. 	}
  45. }
  46.  
  47. ll dfs(int x, int y)
  48. {
  49. 	if(dp[x][y]) return dp[x][y];
  50. 	for(int i=0; i<4; i++)
  51. 	{
  52. 		int nx = x + mov[i][0];
  53. 		int ny = y + mov[i][1];
  54. 		if(nx <1 || nx > n || ny < 1 || ny > n) continue;
  55. 		if(dis[x][y] > dis[nx][ny])
  56. 		{
  57. 			dp[x][y] += dfs(nx,ny);
  58. 		}
  59. 	}
  60. 	return dp[x][y];
  61. }
  62.  
  63. int main()
  64. {
  65. 	while(cin>>n)
  66. 	{
  67. 		memset(dp, 0, sizeof dp);
  68. 		memset(dis, 0, sizeof dis);
  69. 		dp[n][n] = 1;
  70. 		
  71. 		for(int i=1; i<=n; i++)
  72. 			for(int j=1; j<=n; j++)
  73. 				cin>>t[i][j];
  74. 			
  75. 		bfs();
  76. 		
  77. 		cout<<dfs(1,1)<<endl;
  78. 	}
  79. 	return 0;
  80. }

D - Free Candies

 UVA - 10118 

题意：四堆糖果，每次从最上面拿一个，手中最多拿五个，如果手里的糖果有相同的，就可以把糖果占为己有，最多可以占有多少对糖果。

思路：遍历所有选法。

  1. #include<iostream>
  2. #include<cstring>
  3. #include<algorithm>
  4.  
  5. using namespace std;
  6.  
  7. const int N = 55;
  8.  
  9. int num[N][N];
  10. int vis[N];
  11. int n;
  12. int dp[N][N][N][N];
  13. int c[N];//这列拿到哪个糖果 
  14.  
  15. int dfs(int k)
  16. {
  17. 	int &rul = dp[c[1]][c[2]][c[3]][c[4]];
  18. 	if(rul != -1) return rul;
  19. 	rul = 0;
  20. 	if(k >= 5) return 0;
  21. 	
  22. 	for(int i=1; i<=4; i++)
  23. 	{
  24. 		if(c[i] == n) continue;
  25. 		c[i]++;
  26. 		if(vis[num[c[i]][i]]) 
  27. 		{
  28. 			vis[num[c[i]][i]] = 0;
  29. 			rul = max(rul, dfs(k-1)+1);
  30. 			vis[num[c[i]][i]] = 1;
  31. 		}
  32. 		else
  33. 		{
  34. 			vis[num[c[i]][i]] = 1;
  35. 			rul = max(rul, dfs(k+1));
  36. 			vis[num[c[i]][i]] = 0;
  37. 		}
  38. 		c[i]--;
  39. 	}
  40. 	return rul;
  41. 	
  42. }
  43.  
  44.  
  45. int main()
  46. {
  47. 	while(cin>>n && n)
  48. 	{
  49. 		for(int i=1; i<=n; i++)
  50. 			for(int j=1; j<=4; j++)
  51. 				cin>>num[i][j];
  52. 		
  53. 		memset(vis, 0, sizeof vis);
  54. 		memset(dp, -1, sizeof dp);
  55. 		memset(c, 0, sizeof c);
  56. 		
  57. 		cout<<dfs(0)<<endl;
  58. 	}
  59. 	return 0;
  60. }

E - Zipper

 HDU - 1501 

Given three strings, you are to determine whether the third string can be formed by combining the characters in the first two strings. The first two strings can be mixed arbitrarily, but each must stay in its original order.

For example, consider forming "tcraete" from "cat" and "tree":

String A: cat
String B: tree
String C: tcraete


As you can see, we can form the third string by alternating characters from the two strings. As a second example, consider forming "catrtee" from "cat" and "tree":

String A: cat
String B: tree
String C: catrtee


Finally, notice that it is impossible to form "cttaree" from "cat" and "tree".

Input

The first line of input contains a single positive integer from 1 through 1000. It represents the number of data sets to follow. The processing for each data set is identical. The data sets appear on the following lines, one data set per line.

For each data set, the line of input consists of three strings, separated by a single space. All strings are composed of upper and lower case letters only. The length of the third string is always the sum of the lengths of the first two strings. The first two strings will have lengths between 1 and 200 characters, inclusive.
 

Output

For each data set, print:

Data set n: yes

if the third string can be formed from the first two, or

Data set n: no

if it cannot. Of course n should be replaced by the data set number. See the sample output below for an example.

Sample Input

  1. 3
  2. cat tree tcraete
  3. cat tree catrtee
  4. cat tree cttaree

Sample Output

  1. Data set 1: yes
  2. Data set 2: yes
  3. Data set 3: no

思路：遍历所有情况的所有状态。

  1. #include<iostream>
  2. #include<cstring>
  3.  
  4. using namespace std;
  5.  
  6. const int N = 210;
  7. int dp[N][N];//当前情况下的匹配状态，0表示未匹配，1表示匹配成功，2表示匹配不成功 
  8. char a[N],b[N],c[2*N];
  9.  
  10. int dfs(int i,int j, int k)
  11. {
  12. 	if(dp[i][j]) return dp[i][j];
  13. 	
  14. 	if(k == strlen(c)) return dp[i][j] = 1; 
  15. 	
  16.  	dp[i][j] = 2;
  17. 	
  18. 	if(a[i] == c[k]) dp[i][j] = dfs(i+1, j, k+1);
  19. 	if(b[j] == c[k] && dp[i][j] != 1) dp[i][j] = dfs(i, j+1, k+1);
  20. 	
  21. 	return dp[i][j];
  22. }
  23.  
  24.  
  25. int main()
  26. {
  27. 	int n;
  28. 	cin>>n;
  29. 	for(int i=1; i<=n; i++)
  30. 	{	
  31. 		scanf("%s %s %s", a,b,c);
  32. 		memset(dp, 0, sizeof dp);
  33. 		if(dfs(0,0,0) == 1) printf("Data set %d: yes\n",i);
  34. 		else printf("Data set %d: no\n",i);
  35. 	}
  36. 	return 0;
  37. }

F - Bone Collector

 HDU - 2602 

Many years ago , in Teddy’s hometown there was a man who was called “Bone Collector”. This man like to collect varies of bones , such as dog’s , cow’s , also he went to the grave …
The bone collector had a big bag with a volume of V ,and along his trip of collecting there are a lot of bones , obviously , different bone has different value and different volume, now given the each bone’s value along his trip , can you calculate out the maximum of the total value the bone collector can get ?

Input

The first line contain a integer T , the number of cases.
Followed by T cases , each case three lines , the first line contain two integer N , V, (N <= 1000 , V <= 1000 )representing the number of bones and the volume of his bag. And the second line contain N integers representing the value of each bone. The third line contain N integers representing the volume of each bone.

Output

One integer per line representing the maximum of the total value (this number will be less than 231).

Sample Input

  1. 1
  2. 5 10
  3. 1 2 3 4 5
  4. 5 4 3 2 1

Sample Output

14

思路：遍历所有情况。

  1. #include<iostream>
  2. #include<cstring>
  3. #include<algorithm>
  4.  
  5. using namespace std;
  6.  
  7. const int N = 1010;
  8.  
  9. struct node{
  10. 	int val;
  11. 	int wei;
  12. }bones[N];
  13.  
  14. int dp[N][N];
  15. int n,v;
  16.  
  17. int dfs(int x, int left)
  18. {
  19. 	if(x > n) return 0;
  20. 	
  21. 	if(dp[x][left]) return dp[x][left];
  22. 	
  23. 	if(bones[x].wei > left)  return dp[x][left] = dfs(x+1, left);
  24. 	
  25. 	return dp[x][left] = max(dfs(x+1, left), dfs(x+1, left-bones[x].wei) + bones[x].val);
  26. 	
  27. }
  28.  
  29.  
  30. int main()
  31. {
  32. 	int t;
  33. 	cin>>t;
  34. 	while(t--)
  35. 	{		
  36. 		cin>>n>>v;
  37. 		for(int i=1; i<=n; i++) cin>>bones[i].val;
  38. 		for(int i=1; i<=n; i++) cin>>bones[i].wei;
  39. 		cout<<dfs(1, v)<<endl;
  40. 		memset(dp, 0, sizeof dp);
  41. 	}
  42. 	return 0;
  43.  }

G - FatMouse and Cheese

HDU - 1078 

有一种游戏是的玩法是这样的：
有一个n*n的格子,每个格子有一个数字。
遵循以下规则:
1. 玩家每次可以由所在格子向上下左右四个方向进行直线移动，每次移动的距离不得超过m
2. 玩家一开始在第一行第一列，并且已经获得该格子的分值
3. 玩家获得每一次移动到的格子的分值
4. 玩家下一次移动到达的格子的分值要比当前玩家所在的格子的分值要大。
5. 游戏所有数字加起来也不大，保证所有数字的和不会超过int型整数的范围
6. 玩家仅能在n*n的格子内移动，超出格子边界属于非法操作
7. 当玩家不能再次移动时，游戏结束
现在问你，玩家所能获得的最大得分是多少？

Input

有多组测试数据
每组测试样例第一行是两个整数n,m (1≤n≤100)(1≤m≤100),当n和m都是-1时为程序结束标志，直接退出即可
之后n行，每行n个数字，描述n*n的格子里的数字

Output

对于每组测试数据输出一行，这一行仅有一个整数，代表玩家所能获得的最高得分

Sample Input

  1. 3 1
  2. 1 2 5
  3. 10 11 6
  4. 12 12 7
  5. -1 -1

Sample Output

37
  1. #include<iostream>
  2. #include<cstring>
  3. #include<algorithm>
  4.  
  5. using namespace std;
  6.  
  7. const int N = 110;
  8.  
  9. int n,m;
  10. int mp[N][N];
  11. int dp[N][N];
  12. int mov[4][2] = {0,1,0,-1,1,0,-1,0};
  13.  
  14. int dfs(int x, int y)
  15. {
  16. 	
  17. 	if(dp[x][y]) return dp[x][y];
  18. 	
  19. 	dp[x][y] = mp[x][y];
  20. 	
  21. 	for(int i=0; i<4; i++)
  22. 		for(int j=1; j<=m; j++)
  23. 		{
  24. 			int nx = x + mov[i][0] * j;
  25. 			int ny = y + mov[i][1] * j;
  26. 			if(nx >= 1 && nx <= n && ny >= 1 && ny <= n && mp[nx][ny] > mp[x][y])
  27. 			dp[x][y] = max(mp[x][y] + dfs(nx, ny), dp[x][y]);
  28. 		}
  29. 	return dp[x][y];
  30. }
  31.  
  32. int main()
  33. {
  34. 	while(cin>>n>>m)
  35. 	{
  36. 		if(n == -1 && m == -1) break;
  37. 		for(int i=1; i<=n; i++)
  38. 			for(int j=1; j<=n; j++)
  39. 				cin>>mp[i][j];
  40. 		cout<<dfs(1,1)<<endl;
  41. 		memset(dp, 0, sizeof dp);
  42. 	}
  43. 	return 0;
  44. }

 

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/weixin_40725706/article/detail/998763
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号