动态规划


动态规划的基本思想是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解，其经过分解的子问题往往不是相互独立的

  • 其解依赖于子问题
  • 子问题的求解是重复的
  • 采用重递归出现的大量重复运算

    如 Fib 数列


    采用动态规划方法
  1. 构造所有子问题的一个表格
  2. 采用自底向上的方法依次求解子问题
  3. 也可以采用自上而下，为避免重复运算，采用 备忘录 或称为 记忆递归 
F[1] = F[0] = 1;//最简单的子问题
for(int i  = 2;i<=n;i++)
{
	F[i] = F[i-1] + F[i-2];
}

//备忘录
long *F = new long[n+1];
//备忘录标志
for(int i = 0;i<=n;i++)
{
	F[i] = 0;
}
long Fi(int n)
{
	if(F(n)>0) return F[n];
	if(n==0||n==1)
	{
		F[n] = 1;
		return F[n];
	}
	return F[n-1]+F[n-2];
}


最长公共子序列

  • 子序列 <X1,X3,X10> 是一个子序列
  • 子串 Xi,Xi+1,Xi+2,Xi+3.....Xi+k

要找到 X = {x1,x2...xm } 和 Y= {y1,y2...yn} 的最长公共子序列

  • 当 xi = yj 时，找到Xi-1和Yj-1的最长公共子序列，然后在尾部加上xi(yj）即可得X和Y的最长公共子序列。
  • 当 xi != yj 时 找到Xi-1 和 Yj的最长子序列 和 Yj-1 和 Xi的最长子序列中的较大值

c[i][j] = 0 i=0,j=0

c[i][j] = c[i-1][j-1]+1 Xi= Yj

c[i][j] = max(c[i][j-1],c[i-1][j]) Xi != Yj

void LCSLength(int m,int n,char *x,char *y,int **c,int **b)
{
	int i,j;
	for( i = 1;i<=m;i++)//初始化
		c[i][0] = 0;
	for(i = 1;i<=n;i++)
		c[0][i] = 0;
	for(i = 1;i<=m;i++)
	{
		for(j = 1;j<=n;j++)
		{
			if(x[i]==y[j])
			{
				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;
			}
		}
	}
}


//打印出最长公共子序列
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);
}



and CJdl 代码送上

/*
二维数组的解法中的最优值二维数组 K 中，每一个K[i][j]的值仅与前一列、上一行、对角线的值有关
可将二维数组 K 压缩成一维数组 Z ，Z[j]对应 K[i][j]；Z[0]存储 K[i][j]对角线的值，Z[j-1]对应 K[i][j]前一列值 K[i][j-1]，Z[j]未改变前的值即对应 K[i][j]上一行的值K[i-1][j] 
*/
int LCS(string X,string Y,int m,int n,string s[]) 
{
	// Z 记录最优值，s 记录最优解 
	int Z[n+1];
	for(int i=0;i<=n;i++)
	{
		Z[i]=0;
		s[i]="";
	}
	for(int i=1;i<=m;i++)
	{
		//Z[0]暂存K[i][j]对角线位置的最优值，s[0]暂存对角线位置的最优解 
		Z[0]=0; 
		s[0]="";
		for(int j=1;j<=n;j++)
		{
			if(X[i]==Y[j])
			{
				swap(s[j],s[0]);
				swap(Z[j],Z[0]);
				Z[j]++;
				s[j]=s[j]+X[i];
			}
			else
			{
				Z[0]=Z[j];
				s[0]=s[j];
				if(Z[j]<Z[j-1])
				{
					Z[j]=Z[j-1];
					s[j]=s[j-1];
				}
			}
		}
	}
	return Z[n];
}


最大子段和


问题描述:给定由n个整数(可能为非负数)组成的序列a1,a2,a3,a4......an,求该序列的子段和的最大值.


动态规划核心更新公式:b[j] = max(b[j-1],0)+a[j]

int MaxSum(int n,vector<int> &a)
{
	vector<int> b(0,a.size());
	int sum = 0,b = 0;
	for(int i = 1;i<n;i++)
	{
		b[i] = max(b[i-1],0) + a[i];
		sum = max(sum,b[i]); 
	}
	return sum;
}