• 动 态 规 划

    一、（what？）

    二、（why？）

    三、（how？）

    四、典型例题分析：

    例题1：神奇的兔子序列

    输入：月数

    输出：兔子数

    思路：

    代码1（函数递归）：

    1. #include
    2. using namespace std;
    3.  
    4. int fib(int n)
    5. {
    6. 	if(n < 1)
    7. 		return -1;
    8. 	else if(n == 1|| n == 2)
    9. 		return 1;
    10. 	else
    11. 		return fib(n-1)+fib(n-2);
    12. }
    13.  
    14. int main()
    15. {
    16. 	int n;
    17. 	cin>>n;
    18. 	cout<<fib(n);
    19. 	return 0;
    20. }

    代码2（数组递归）：

    1. #include
    2. using namespace std;
    3.  
    4. int fib(int n)
    5. {
    6. 	if(n < 1) return -1;
    7. 	int F[n+1];
    8. 	F[1] = 1, F[2] = 1;
    9. 	for(int i = 3; i <= n; i++)
    10. 		F[i] = F[i-1]+F[i-2];
    11. 	return F[n];
    12. }
    13.  
    14. int main()
    15. {
    16. 	int n;
    17. 	cin>>n;
    18. 	cout<<fib(n);
    19. 	return 0;
    20. }

    例题2：孩子有多像爸爸——最长公共子序列

     暴力搜索

    举个简单的暴力搜索的

    1. #include
    2. using namespace std;
    3. int main()
    4. {
    5. 	char s[7]={'A','B','C','B','A','D','B'};
    6. 	
    7. 	for(int k=0;k<=7;k++)
    8. 	{
    9. 		for(int i=k;i<=7;i++)
    10. 		{
    11. 			for(int j=k;j
    12. 			{
    13. 				cout<
    14. 			}
    15. 			cout<
    16. 		}	
    17. 	}
    18. 	
    19. 	return 0;
    20.  }

     显示所有子串：

     求其中一个子串的数组：

    1. #include
    2. using namespace std;
    3. int main()
    4. {
    5. 	char s[7] = {'A','B','C','B','A','D','B'};
    6. 	//char ss[6] = {'B','C','B','A','A','C'};
    7. 	
    8. 	string str1[100],str2[100];
    9. 	int len1=0,len2=0;
    10. 	
    11. 	for(int k=0;k<=7;k++)
    12. 	{
    13. 		for(int i=k;i<=7;i++)
    14. 		{
    15. 			for(int q=k;q
    16. 			{
    17. 				str1[len1]+=s[q];
    18. 			}
    19. 			len1++;
    20. 		}	
    21. 	}	
    22. 	for(int k=0;k
    23. 	{
    24. 		cout<
    25. 	}	
    26. 	return 0;
    27.  }

     输出：

    题解代码：

    1. #include
    2. #include
    3. using namespace std;
    4.  
    5. const int MAX=1000;
    6.  
    7. char s[MAX],ss[MAX];
    8.  
    9. string str1[MAX],str2[MAX];
    10.  
    11. int len1=0,len2=0;
    12.  
    13. int main()
    14. {
    15. 	//char s[7] = {'A','B','C','B','A','D','B'};
    16. 	//char ss[6] = {'B','C','B','A','A','C'};
    17. 	
    18. 	//string str1[100],str2[100];
    19. 	//int len1=0,len2=0;
    20. 	
    21. 	string st1,st2;
    22. 	cin>>st1>>st2;
    23. 	int i=0,j=0;
    24. 	while(ilength())
    25. 	{
    26. 		s[i]=st1[i];
    27. 		i++;
    28. 	}
    29. 	while(jlength())
    30. 	{
    31. 		ss[j]=st2[j];
    32. 		j++;
    33. 	}
    34. 	
    35. 	//存入第一个子串数组 
    36. 	for(int k=0;k<=7;k++)
    37. 	{
    38. 		for(int i=k;i<=7;i++)
    39. 		{
    40. 			for(int q=k;q
    41. 			{
    42. 				str1[len1]+=s[q];
    43. 			}
    44. 			len1++;
    45. 		}	
    46. 	}
    47. 	/*	
    48. 	for(int k=0;k
    49. 	{
    50. 		cout<
    51. 	}	*/
    52. 	//存入第二个子串数组
    53. 	for(int k=0;k<=6;k++)
    54. 	{
    55. 		for(int i=k;i<=6;i++)
    56. 		{
    57. 			for(int q=k;q
    58. 			{
    59. 				str2[len2]+=ss[q];
    60. 			}
    61. 			len2++;
    62. 		}	
    63. 	}	
    64. 	/*	
    65. 	for(int k=0;k
    66. 	{
    67. 		cout<
    68. 	}	 
    69. 	*/
    70. 	int temp=0,max=-1000;
    71. 	string answer;
    72. 	for(int i=0;i
    73. 	{
    74. 		string strr1=str1[i];
    75. 		for(int j=0;j
    76. 		{
    77. 			if(str2[j]==strr1)
    78. 			{
    79. 				temp=strr1.length();
    80. 				if(temp>=max)
    81. 				{
    82. 					max=temp;
    83. 					answer=strr1;
    84. 				}
    85. 			}
    86. 		}	
    87. 	} 
    88. 	cout<
    89. 	return 0;
    90.  }

    结果：

    *注：这并不是例题的解法，只是对暴力搜索举个例子，二者并无关联！

    原理题的条件子串是从父亲的基因中取一些值并非一定连续！！！

     下面，用动态规划算法解决此问题

    算法设计：

    图解算法：

     

     

     

     

     

    伪代码：

    1. Void LCSL()
    2. {
    3.     int I,j;
    4.     for(I = 1;I <= len1;i++)    //控制s1序列
    5.       for(j = 1;j <= len2;j++)  //控制s2序列
    6.       {
    7.         if(s1[i-1]==s2[j-1])    //字符下标从0开始
    8.         {   //如果当前字符相同，则公共子序列的长度为该字符前的最长公共序列+1
    9.             c[i][j] = c[i-1][j-1]+1;
    10.             b[i][j] = 1;
    11.         }
    12.         else
    13.         {
    14.             if(c[i][j-1]>=c[i-1][j]) //两者找最大值，并记录最优策略来源
    15.             {
    16.                   c[i][j] = c[i][j-1];
    17.                   b[i][j] = 2;
    18.             }
    19.             else
    20.             {
    21.                   c[i][j] = c[i-1][j];
    22.                   b[i][j] = 3;
    23.             }
    24.         }
    25.      }
    26. }

    1. Void print(int I, int j)//根据记录下来的信息构造最长公共子序列（从b[i][j]开始递推）
    2. {
    3.     if(i==0 || j==0) return;
    4.     if(b[i][j]==1)
    5.     {
    6.         print(i-1,j-1);
    7.         cout<-1];
    8.     }
    9.     else if(b[i][j]==2)
    10.               print(I,j-1);
    11.           else print(i-1,j);
    12. }

    代码：

    1. #include
    2. #include
    3. using namespace std;
    4. const int N = 1002;//数组最大长度 
    5. int c[N][N], b[N][N];//c：公共子序列长度。b：答案路径
    6. char s1[N], s2[N];
    7. int len1, len2;
    8.  
    9.  
    10. //动态规划查询最大子序列函数 
    11. void LCSL()
    12. {
    13. 	int i, j;
    14. 	for (i = 1; i <= len1; i++)//控制s1序列
    15. 	{
    16. 		for (j = 1; j <= len2; j++)//控制s2序列
    17. 		{
    18. 			//动态规划开始
    19. 			if (s1[i - 1] == s2[j - 1])//字符下标从0开始 
    20. 			{//如果字符相同，公共子序列的长度为该字符前的最长公共子序列（左上角）+1 
    21. 				c[i][j] = c[i - 1][j - 1] + 1;
    22. 				b[i][j] = 1;//此情况标记为1 
    23. 			}
    24. 			else
    25. 			{//如果字符不相等的子序列长度 
    26. 				if (c[i][j - 1] >= c[i - 1][j])
    27. 				{//如果上面的大于左面，子序列长度为上值 
    28. 					c[i][j] = c[i][j - 1];
    29. 					b[i][j] = 2;//取上值为2 
    30. 				}
    31. 				else
    32. 				{//如果左大于上，取左值 
    33. 					c[i][j] = c[i - 1][j];
    34. 					b[i][j] = 3;//取左值为3 
    35. 				}
    36. 			}
    37. 		}
    38. 	}
    39. 	for (i = 0; i <= len1; i++)
    40. 	{
    41. 		for(j = 0; j <= len2; j++)
    42. 		{
    43. 			cout << c[i][j];
    44. 		}
    45. 		cout << endl;
    46. 	}
    47. }
    48.  
    49. //输出最优路径的函数（因为是函数递归，所以经过倒退能得到正序路径） 
    50. void print(int i, int j)//从b[i][j]开始递推 
    51. {
    52. 	if (i == 0 || j == 0) return;//如果有一个序列递归完了就结束递归
    53. 	if (b[i][j] == 1)
    54. 	{//说明此时s1[i-1]=s2[j-1],b[i][j]的值来自c左上角 
    55. 		print(i - 1, j - 1);//递归去左上角 
    56. 		cout << s1[i - 1];
    57. 	}
    58. 	else if (b[i][j] == 2)
    59. 	{//s1[i-1]与s2[j-1]不等，b[i][j]值来自c上 
    60. 		print(i, j - 1);
    61. 	}
    62. 	else
    63. 	{//字符不等取值来自左 
    64. 		print(i - 1, j);
    65. 	}
    66. }
    67.  
    68. int main()
    69. {
    70. 	int i, j;
    71. 	cout << "输入字符串s1:" << endl;
    72. 	cin >> s1;
    73. 	cout << "输入字符串s2:" << endl;
    74. 	cin >> s2;
    75. 	len1 = strlen(s1);//求char型数组的长度
    76. 	len2 = strlen(s2);
    77.  
    78. 	for (i = 0; i <= len1; i++)
    79. 	{
    80. 		c[i][0] = 0;//初始化第一行	
    81. 	}
    82. 	for (j = 0; j <= len2; j++)
    83. 	{
    84. 		c[0][j] = 0;//初始化第一列	
    85. 	}
    86.  
    87. 	LCSL();//求最长子序列
    88. 	cout << "最长子序列长度为：" << c[len1][len2] << endl;
    89. 	cout << "最长公共子序列是：";
    90. 	print(len1, len2);
    91. 	return 0;
    92. }

    输出： 

    例题3：DNA基因鉴定——编辑距离

     算法设计：

    算法图解：

     

     

    伪代码：

    1. int editdistance(char *str1, char *str2)
    2. {
    3.      int len1 = strlen(str1);      //计算字符串长度
    4.      int len2 = strlen(str2); 
    5.      for(int i=0;i<=len1;i++)      //当第二个串长度为0，编辑距离初始化为i
    6.           d[i][0]= i;
    7.      for(int j=0;j<=len2;j++)      //当第一个串长度为0，编辑距离初始化为j
    8.           d[0][j]=j;
    9.      for(int i=1;i <=len1;i++)     //遍历两个字符串
    10.      {
    11.           for(int j=1;j<=len2;j++)
    12.           {
    13.                int diff;//判断str[i]是否等于str2[j],相等为0，不相等为1
    14.                if(str1[i-1] == str2[j-1]) //相等
    15.                      diff = 0 ;
    16.                else
    17.                      diff = 1 ;
    18.                int temp = min(d[i-1][j] + 1, d[i][j-1] + 1);//先两者取最小值
    19.                d[i][j] = min(temp, d[i-1][j-1] + diff);//再取最小值，
    20.                      //相当于三者取最小值d[i-1][j] + 1, d[i][j-1] + 1，d[i-1][j-1] + diff
    21.           }
    22.      }
    23.      return d[len1][len2];
    24. }

     完整代码：

    1. #include
    2. #include
    3. using namespace std;
    4. const int N = 100;
    5. char str1[N],str2[N];
    6. int d[N][N];//d[i][j]表示的str1前i个字符的str2前j个字符的编辑距离
    7.  
    8. int StrLen(char *s)//求字符串长度 
    9. {
    10. 	int i=0;
    11. 	while(s[i]!='\0')
    12. 	{
    13. 		i++;	
    14. 	}	
    15. 	return i;
    16. } 
    17.  
    18. int min(int a,int b)
    19. {
    20. 	return a//返回较小值 
    21. }
    22.  
    23. int editdistance(char *str1,char *str2)
    24. {
    25. 	int len1=StrLen(str1);
    26. 	int len2=StrLen(str2);	
    27. 	//初始化
    28. 	for(int i=0;i<=len1;i++)
    29. 	{//第二个串长度为0，编辑距离初始化为i 
    30. 		d[i][0]	= i;
    31. 	} 
    32. 	for(int j=0;j<=len2;j++)
    33. 	{//第二个串长度为0，编辑距离初始化为j
    34. 		d[0][j]	= j;
    35. 	}
    36. 	//遍历两个字符串 
    37. 	for(int i=1;i<=len1;i++)
    38. 	{
    39. 		for(int j=1; j<=len2;j++)
    40. 		{
    41. 			int diff;//判断字符是否相等，相等不需要编辑+0，不相等+1
    42. 			if(str1[i-1] == str2[j-1])
    43. 			{
    44. 				diff=0;
    45. 			}
    46. 			else
    47. 			{
    48. 				diff=1;	
    49. 			} 
    50. 			int temp=min(d[i-1][j]+1,d[i][j-1]+1);
    51. 			d[i][j] = min(temp,d[i-1][j-1]+diff);//连去两次两个求最小值等价于三个求最小值 
    52. 		}
    53. 	}
    54. 	for(int i=0;i<=len1;i++)
    55. 	{
    56. 		for(int j=0;j<=len2;j++)
    57. 		{
    58. 			cout<
    59. 		}
    60. 		cout<
    61. 	}
    62. 	return d[len1][len2]; 
    63. } 
    64. int main()
    65. {
    66. 	cin>>str1>>str2;
    67. 	cout<<editdistance(str1,str2);
    68. 	return 0;
    69. }

     输入输出：

    例题4：长江一日游——游艇租赁

    算法设计： 

     算法图解：

    伪代码：

    1. void rent()
    2. {
    3.      int i,j,k,d;
    4.      for(d=3;d<=n;d++) //将问题分为小规模d
    5.      {
    6.           for(i=1;i<=n-d+1;i++)
    7.                {
    8.                     j=i+d-1;
    9.                     for(k=i+1;k//记录每一个小规模内的最优解
    10.                     {
    11.                          int temp;
    12.                          temp=m[i][k]+m[k][j];
    13.                          if(temp
    14.                                {
    15.                                  m[i][j]=temp;
    16.                                  s[i][j]=k;
    17.                                }
    18.                     }
    19.                }
    20.      }
    21. }

     

    1. void print(int i,int j)
    2. {
    3.      if(s[i][j]==0 )
    4.      {
    5.           cout << "--"<
    6.           return ;
    7.      }
    8.      print(i,s[i][j]);
    9.      print(s[i][j],j);
    10. }

     完整代码：

    1. //program 4-3
    2. #include
    3. using namespace std;
    4. const int ms = 1000;
    5. int r[ms][ms],m[ms][ms],s[ms][ms];    //i到j站的租金
    6. int n;            //共有n个站点
    7. void rent()
    8. {
    9.      int i,j,k,d;
    10.      for(d=3;d<=n;d++) //将问题分为小规模为d
    11.      {
    12.          for(i=1;i<=n-d+1;i++)
    13.               {
    14.                    j=i+d-1;
    15.                    for(k=i+1;k//记录每一个小规模内的最优解
    16.                    {
    17.                         int temp;
    18.                         temp=m[i][k]+m[k][j];
    19.                         if(temp
    20.                              {
    21.                                 m[i][j]=temp;
    22.                                 s[i][j]=k;
    23.                              }
    24.                    }
    25.               }
    26.      }
    27. }
    28. void print(int i,int j)
    29. {
    30.      if(s[i][j]==0 )
    31.      {
    32.          cout << "--"<
    33.          return ;
    34.      }
    35.      print(i,s[i][j]);
    36.      print(s[i][j],j);
    37. }
    38. int main()
    39. {
    40.      int i,j;
    41.      cout << "请输入站点的个数 n：";
    42.      cin >> n;
    43.      cout << "请依次输入各站点之间的租金：";
    44.      for(i=1;i<=n;i++)
    45.           for(j=i+1;j<=n;++j)
    46.           {
    47.               cin>>r[i][j];
    48.               m[i][j]=r[i][j];
    49.           }
    50.      rent();
    51.      cout << "花费的最少租金为：" <1][n] << endl;
    52.      cout <<"最少租金经过的站点："<<1;
    53.      print(1,n);
    54.      return 0;
    55. }

    输入输出：

    例题5：快速计算——矩阵连乘

     算法设计：

    图解算法：

     伪代码：

    1. void print(int i,int j)
    2. {
    3.      if( i == j )
    4.      {
    5.          cout <<"A[" << i << "]";
    6.          return ;
    7.      }
    8.      cout << "(";
    9.      print(i,s[i][j]);
    10.      print(s[i][j]+1,j);
    11.      cout << ")";
    12. }

     完整代码：

    1. //program 4-4
    2. #include
    3. #include
    4. #include
    5. using namespace std;
    6. const int msize = 100;
    7. int p[msize];
    8. int m[msize][msize],s[msize][msize];
    9. int n;
    10. void matrixchain()
    11. {
    12.      int i,j,r,k;
    13.      memset(m,0,sizeof(m));
    14.      memset(s,0,sizeof(s));
    15.      for(r = 2; r <= n; r++)          //不同规模的子问题
    16.      {
    17.           for(i = 1; i <= n-r+1; i++)
    18.           {
    19.               j = i + r - 1;
    20.               m[i][j] = m[i+1][j] + p[i-1] * p[i] * p[j];  //决策为k=i的乘法次数
    21.               s[i][j] = i;            //子问题的最优策略是i;
    22.               for(k = i+1; k < j; k++) //对从i到j的所有决策，求最优值，记录最优策略
    23.                {
    24.                     int t = m[i][k] + m[k+1][j] + p[i-1] * p[k] * p[j];
    25.                     if(t < m[i][j])
    26.                     {
    27.                           m[i][j] = t;
    28.                           s[i][j] = k;
    29.                     }
    30.                }
    31.           }
    32.      }
    33. }
    34. void print(int i,int j)
    35. {
    36.      if( i == j )
    37.      {
    38.           cout <<"A[" << i << "]";
    39.           return ;
    40.      }
    41.      cout << "(";
    42.      print(i,s[i][j]);
    43.      print(s[i][j]+1,j);
    44.      cout << ")";
    45. }
    46. int main()
    47. {
    48.      cout << "请输入矩阵的个数 n：";
    49.      cin >> n;
    50.      int i ,j;
    51.      cout << "请依次输入每个矩阵的行数和最后一个矩阵的列数：";
    52.      for (i = 0; i <= n; i++ )
    53.           cin >> p[i];
    54.      matrixchain();
    55.      print(1,n);
    56.      cout << endl;
    57.      cout << "最小计算量的值为：" << m[1][n] << endl;
    58. }

     输入输出：

    例题6：切呀切披萨——最优三角剖分

    例题7：小石子游戏——石子合并

    例题8：大卖场购物车——0-1背包问题

     算法设计：

     图解算法：

    伪代码：

    1. for(i=1;i<= n;i++)           //计算c[i][j]
    2.           for(j=1;j<=W;j++)
    3.                if(j//当物品的重量大于购物车的容量，则不放此物品
    4.                     c[i][j] = c[i-1][j];
    5.                else          //否则比较此物品放与不放是否能使得购物车内的价值最大
    6.                     c[i][j] = max(c[i-1][j],c[i-1][j-w[i]] + v[i]);
    7.      cout<<"装入购物车的最大价值为:"<

     

    1. //逆向构造最优解
    2. j=W;
    3. for(i=n;i>0;i--)
    4.     if(c[i][j]>c[i-1][j])
    5.     {
    6.          x[i]=1;
    7.          j-=w[i];
    8.     }
    9.     else
    10.         x[i]=0;
    11. cout<<"装入购物车的物品为:";
    12. for(i=1;i<=n;i++)
    13.     if(x[i]==1)
    14.          cout<"  ";

     完整代码：

    1. //program 4-7
    2. #include 
    3. #include
    4. using namespace std;
    5. #define maxn 10005
    6. #define M 105
    7. int c[M][maxn];         //c[i][j] 表示前i个物品放入容量为j购物车获得的最大价值
    8. int w[M],v[M];          //w[i] 表示第i个物品的重量，v[i] 表示第i个物品的价值
    9. int x[M];               //x[i]表示第i个物品是否放入购物车
    10. int main(){
    11.      int i,j,n,W;       //n表示n个物品，W表示购物车的容量
    12.      cout << "请输入物品的个数n：";
    13.      cin >> n;
    14.      cout << "请输入购物车的容量W：";
    15.      cin >> W;
    16.      cout << "请依次输入每个物品的重量w和价值v，用空格分开：";
    17.      for(i=1;i<=n;i++)
    18.           cin>>w[i]>>v[i];
    19.      for(i=0;i<=n;i++)  //初始化第0列为0
    20.           c[i][0]=0;
    21.      for(j=0;j<=W;j++)  //初始化第0行为0
    22.           c[0][j]=0;
    23.      for(i=1;i<= n;i++) //计算c[i][j]
    24.           for(j=1;j<=W;j++)
    25.                if(j//当物品的重量大于购物车的容量，则不放此物品
    26.                     c[i][j] = c[i-1][j];
    27.                else    //否则比较此物品放与不放是否能使得购物车内的价值最大
    28.                     c[i][j] = max(c[i-1][j],c[i-1][j-w[i]] + v[i]);
    29.      cout<<"装入购物车的最大价值为："<
    30.      //逆向构造最优解
    31.      j=W;
    32.      for(i=n;i>0;i--)
    33.           if(c[i][j]>c[i-1][j])
    34.           {
    35.                x[i]=1;
    36.                j-=w[i];
    37.           }
    38.           else
    39.                x[i]=0;
    40.      cout<<"装入购物车的物品为：";
    41.      for(i=1;i<=n;i++)
    42.           if(x[i]==1)
    43.                cout<"  ";
    44.      return 0;
    45. }

    输入输出：

    例题9：快速定位——最优二叉搜索

  • 相关阅读:
    【m_listCtrl !=NULL有多个运算符与操作数匹配】2023/9/21 上午11:03:44
    C2基础设施威胁情报对抗策略
    GC如何判断对象可以被回收
    pycharm基本使用（常用快捷键）
    2024国际生物发酵展畅想未来-势拓伺服科技
    spring cloud alibaba nacos搭建最小可运行微服务
    成员变量为动态数据时不可轻易使用
    SQL存储过程详解
    【新笔记本环境配置】win10下 Anaconda+Vscode+MobaXterm安装
    下列程序的运行结果是 #include ＜stdio.h＞ void main() { int x = 10, y = 20, z = 30；
  • 原文地址：https://blog.csdn.net/qq_51701007/article/details/122666147