【算法】动态规划

一、基础知识

动态规划的基本思想：将待求解问题分解成若干个子问题，如果各个子问题不是独立的，不同的子问题的个数只是多项式量级，为避免大量的重复计算，用一个表记录所有已解决的子问题的答案，而在需要的时候再找出已求得的答案。
分治与动态规划算法的异同：
相似之处:

1. 都可以将大问题划分为小问题求解。
2. 都需要重叠子问题的最优解。

不同之处:

1. 分治算法是自上而下,递归求解,然后合并结果。动态规划是自下而上,从更小的子问题开始递推。

2. 分治算法对每个子问题只计算一次,不会重复计算。动态规划算法会存储每个子问题的解,重复使用,避免重复计算。

3. 分治算法不需要存储中间结果,只存储最终结果。动态规划需要创建一个表来存储各个子问题的解。

4. 分治算法对每个子问题的解需要进行合并,而动态规划只需要简单地查表即可得到解。

5. 分治算法的时间复杂度较高,常为O(nlogn)。动态规划能达到O(n)的时间复杂度。

   总之,分治算法采用自上而下的分解方式,只存储最终结果,要进行结果合并,效率较低。动态规划采用自下而上递推的方式,存储每个子问题的最优解,通过查表得到最终解,效率较高。

理解动态规划算法的基本要素：

1. 最优子结构性质：问题的最优解包含了其子问题的最优解。
2. 重叠子问题性质：有些子问题被反复计算多次。

动态规划算法求解问题的步骤：

1. 找出最优解的性质，并刻画其结构特征
2. 递归地定义最优值
3. 以自底向上的方式计算出最优值
4. 构造最优解

二、矩阵连乘问题

伪代码：

//用动态规划法求解
void MatrixChain(int *p，int n，int **m，int **s)
{for (int i = 1; i <= n; i++) m[i][i] = 0;//矩阵链长度为1for (int r = 2; r <= n; r++)   //r为矩阵链长度，从2…nfor (int i = 1; i <= n - r+1; i++) {//遍历所有长度是r的子问题。//对于每一个给定的链长r，左边界为i，右边界为jint j=i+r-1;m[i][j] = +∞; s[i][j] = i;//记录断开位置，即加括号的位置for (int k = i; k < j; k++){//矩阵链的分隔位置从第i个矩阵…第j-1个矩阵int t = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j];if (t < m[i][j]) { m[i][j] = t; s[i][j] = k;}}}
}

三、最长公共子序列问题

int  LCSLength(char *x,char *y,int  c[ ][N],int  b[ ][N])
{     //x和y的长度     int m=strlen(x),n=strlen(y);  int i,j;  //初始化c[][]  for (i = 0; i <= m; i++) c[i][0] = 0;  for (i = 0; i <= n; i++) c[0][i] = 0;  //计算c[][]for (i = 1; i <= m; i++)   for (j = 1; j <= n; j++){//如果两个字符相同,左上方的值加1   if (x[i-1]==y[j-1]) {    c[i][j]=c[i-1][j-1]+1; b[i][j]=1;    }   //如果不相同,取左方和上方的最大值  else if (c[i-1][j] >= c[i][j-1]) {     c[i][j]=c[i-1][j]; b[i][j]=2;  }  else { c[i][j]=c[i][j-1]; b[i][j]=3; }  }  //返回最长公共子序列长度return  c[m][n];
}
//通过b[][]回溯构造最长公共子序列 
void LCS(int i,int j,char *x,int **b)  
{   //到达边界,返回  if (i ==0 || j==0) return;     //向左上方移动 if (b[i][j]== 1){ LCS(i-1,j-1,x,b); cout<<x[i]; }     //向左方移动else if (b[i][j]== 2) LCS(i-1,j,x,b);   //向上方移动else LCS(i,j-1,x,b);  
}

四、最大子段和问题

int maxSum(int a[],int n,int &begin,int &end){int sum=0;   //结果,最大子序列和int b=0;     //当前和for(int i=0;i<n;i++){if(b>0) b+=a[i]; //如果b大于0,加上当前元素 else{  b=a[i];   //如果b等于0,重新开始,b赋值为当前元素值begin=i;  //记录开始位置  }if(b>sum){ //如果当前和大于结果,更新结果和结尾位置 sum=b;   end=i;  }   }return sum;   //返回结果
} 

五、0-1背包问题

int  Knapsack(int v[], int w[], int c, int n, m[][])  
{     //初始化第一行和第一列,均为0for(int i=0;i<=n;i++)  m[i][0]=0;  for(int j=0;j<=c;j++)  m[0][j]=0;  //自底向上计算每个子问题的最优值for(i=1;i<=n;i++) for(j=1;j<=c;j++){     //如果不能装下,最大价值就是不考虑该物品的价值if(j<w[i]) m[i][j]=m[i-1][j];     //如果能装下,取决于装入或不装入该物品的最大值elsem[i][j]=max(m[i-1][j], m[i-1][j-w[i]]+v[i]);}  //返回总的最大价值return m[n][c];
}