[数据结构与算法]动态规划算法

动态规划

动态规划的性质：
（1）最优化原理：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。
（2）无后效性：即某阶段状态（定义的新子问题）一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与其以前的状态有关。

动态规划的步骤：
（1）刻画一个最优解的结构特征

• 根据问题类型的规模和基本单位，把问题分为若干个阶段。在划分阶段时，注意确保子问题也是最优解，即通过剪贴法证明这个问题具有最优子结构（可以用动态规划解决问题）。

（2）递归地定义最优解的值

• 具体表达出子问题的状态转移方程，一般为
• dp[i][j]=max{ dp[i][k] , dp[k+1][j] }，当然具体问题要具体分析，首先明确所使用的参数所代表的具体含义，在找到转移方程后记得标注变量范围，其次，寻找问题的出口。

3.计算最优解的值，通常采用自底向上的方法

• 借助列出的状态转移方程，可以画出二位表格，先借助某一个具体事例熟练自底向上的计算步骤，进一步理解x，y轴的含义，并找到初始化的值（初值），从底部开始计算，直到计算出最终的目标解。

4.利用计算出的信息构造一个最优解

• 通常这一步需要借助辅助表格来记录动态规划过程中每一个子问题的最优解的选择，借助这个辅助表格，从顶部开始，依次遍历，直到最优解的输出。

1.矩阵链连乘问题

题目描述

给定n个矩阵｛A1,A2,…,An｝，其中Ai与Ai+1是可乘的，i=1，2…，n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序 计算矩阵连乘积需要的数乘次数最少。

输入数据：共m+1行；第一行为测试数据的组数m；以后每行n+1个正 整数，表示n个矩阵的行列值。

样例输出：最少次数及连乘的计算次序。
样例输入：
1
5 10 4 6 10 2
样例输出：
348
(A1(A2(A3(A4A5))))

下面用动态规划方法来求解矩阵链的最优解的方案，按照动态规划4个步骤进行：
1.刻画一个最优解的结构特征

• 对于M1,M2,M3,…Mn，假设在M_k点进行分裂，则其子问题为(M_i,M_i+1,…M_k)，和(M_k+1,M_k+2,M_j)的最优链乘问题，
• 借助剪贴法，对于cost(i,k)，假设(M_i,M_i+1,.M_l）（M_l+1…M_k)不是子问题的最优解，
• cost’ = (M_i,M_i+1,.M_l‘）（M_l’+1…M_k)以l‘为断点的子问题为最优解，
• 那么对于cost(i,j)’ = cost’ + c > cost(i,j) 成为原问题的最优解
• 假设不符合，即符合最优子结构的性质，可以使用动态规划

2.递归地定义最优解的值

• cost[i][j]代表从M_i ——M_j的花销最小值，而cost的值是取自不同断点k

• cost[i][j] = min{ cost[i][k] + cost[k+1][j]+ r(i-1)r(k)r(j) },

• k代表不同切割点，取值1<=k<j; 由常识也可以看出 i<=j，且 i==j 时没有花费。

• 对于r(i-1)r(k)r(j)代表此次合并两个子矩阵所要花费的代价。

• 由此推出状态转移方程：
  ①如果i=j，cost[i,j]=0
  ②如果i<j，cost[i][j] = min{ cost[i][k] + cost[k+1][j]+ r(i-1)r(k)r(j) }, i<=k<j

• 时间复杂度：O(n³)

3.计算最优解的值，通常采用自底向上的方法

• 以
  1
  5 10 4 6 10 2 为例

• 具体以cost[1][3]为例，其最小值取自于
• cost[1][1] + cost[2][3] + r₀r₁r₃ =0+240+5106=540
• cost[1][2] + cost[3][3] + r₀r₂r₃ =200+546=320
• 取k=2时，cost[1][3]最小

4.利用计算出的信息构造一个最优解

• 设置一个二位数组额外记录当前取得最小值来自于那个分裂点k,
  
  发现flag[1][3]值为2，即最小化费是在k=2的切割

代码：

#include<stdio.h>
int m[50][50];
int flag[50][50];				//标记分割字段 
int r[50];
void screen(int *r,int n){
	for(int i=1;i<n;i++)		//斜对角线为0 
		m[i][i]=0;		
		
	for(int k=2;k<n;k++){
		for(int i=1;i<=n-k;i++){
			int j=i+k-1;
			
			m[i][j]=m[i+1][j]+r[i-1]*r[i]*r[j];		//k=i分割时
			flag[i][j]=i;
			for(int l=i+1;l<j;l++){
				int num=m[i][l]+m[l+1][j]+r[i-1]*r[l]*r[j];
				if(num<m[i][j]){
					m[i][j]=num;
					flag[i][j]=l;
				}
			}
		}
	}
	for(int i=1;i<n;i++){
		for(int j=1;j<n;j++){
			printf("%4d",m[i][j]);
		}
		printf("\n");
	}
	printf("%d\n",m[1][n-1]);
}
void printScreen(int i,int j){
	if(i==j){
		printf("A%d",i);
		return;
	}
	printf("(");
	printScreen(i,flag[i][j]);			//打印k左边 
	printScreen(flag[i][j]+1,j);		//打印k右边 
	printf(")"); 
	
} 
int main(){
	int n,m;
	scanf("%d",&m);
	for(int k=0;k<m;k++){
		int n=0;
		int num;
		while(scanf("%d",&num)){
			r[n++]=num;
		}
		screen(r,n);			//求矩阵 
		printScreen(1,n-1);		//打印结果 
	}
}