【算法】动态规划
一、基础知识
动态规划的基本思想：将待求解问题分解成若干个子问题，如果各个子问题不是独立的，不同的子问题的个数只是多项式量级，为避免大量的重复计算，用一个表记录所有已解决的子问题的答案，而在需要的时候再找出已求得的答案。
分治与动态规划算法的异同：
相似之处:
- 都可以将大问题划分为小问题求解。
- 都需要重叠子问题的最优解。
不同之处:
-
分治算法是自上而下,递归求解,然后合并结果。动态规划是自下而上,从更小的子问题开始递推。
-
分治算法对每个子问题只计算一次,不会重复计算。动态规划算法会存储每个子问题的解,重复使用,避免重复计算。
-
分治算法不需要存储中间结果,只存储最终结果。动态规划需要创建一个表来存储各个子问题的解。
-
分治算法对每个子问题的解需要进行合并,而动态规划只需要简单地查表即可得到解。
-
分治算法的时间复杂度较高,常为O(nlogn)。动态规划能达到O(n)的时间复杂度。
总之,分治算法采用自上而下的分解方式,只存储最终结果,要进行结果合并,效率较低。动态规划采用自下而上递推的方式,存储每个子问题的最优解,通过查表得到最终解,效率较高。
理解动态规划算法的基本要素：
- 最优子结构性质：问题的最优解包含了其子问题的最优解。
- 重叠子问题性质：有些子问题被反复计算多次。
动态规划算法求解问题的步骤：
- 找出最优解的性质，并刻画其结构特征
- 递归地定义最优值
- 以自底向上的方式计算出最优值
- 构造最优解
二、矩阵连乘问题
伪代码：
//用动态规划法求解
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];
}