第十四周DP算法总结

这周自己主要再看DP算法的博客，感觉DP这一部分内容确实比之前的都要麻烦一些，最后攻克这一部分难题还是挺好的。 这周自己总结了一些题型，以及一些方法思路，最后再把动态规划和之前的分治和贪心做一下比较。下面是详细的总结。

动态规划就是将一个复杂的问题分解成几个子问题，通过综合子问题的最优解来得到原问题的最优解。一开始我一看那个状态转移方程我就发懵，但是从最简单的题目的状态转移方程入手，发现还是可以的，能看懂一部分内容了。

动态规划的一般做题步骤，先要判断是不是有有重叠子问题和最优子结构，然后再划分阶段，分成若干个小问题，然后确定状态和状态变量，列出状态转移方程（数组形式），接下来找出边界条件，最后递推求解即可。记忆化搜索的思路也是贯穿在了这部分很多题目当中，代码效率得到很大提高。

最大连续子序列和问题，这一类问题用枚举或者前缀和的方式肯定不行的，复杂度高。列出状态转移方程，dp[i]=max{A[i]，dp[i-1]+A[i]}，一开始我是没看懂的，但是仔细一想还是挺巧秒的，用dp[i]表示以A[i]作为末尾的连续序列的最大和，然后求解dp数组。考虑到只有两种情况，一个情况是最大和的连续序列只有一个元素，另一种情况是这个连续序列有很多元素，这个时候最大和就是以前面一个元素为结尾的连续子段的最大和加上当前的元素，就是dp[i-1]+A[i]。这两种情况都讨论完了，求解最大值就是取这两种情况的最大值就行了，然后列出状态转移方程dp[i]=max{A[i]，dp[i-1]+A[i]}就很好理解了，总体来说这类题目还是挺好理解的。

数塔问题，题意是说，一些数字排成数塔的形状，第一层有一个数字，第二层有两个数字，以此类推，从第一层走到第n层，每次只能走下一层连接的两个数字中的一个，最后将经过的数字相加，问得到的最大值是多少。首先确定的是，这个题一定有最优解。枚举从一个数字出发到达底层的所有路径时，就把这个最大和记录下来，可以避免重复计算。可以让dp[i][j]表示从第i行第j列开始到达底层得到的最大和，因为是要求从顶层开始的，所以dp[1][1]就是最终解。因为一个数字下面有两个分支，所以要取其中最大的一个，再加上这个数字就是目前得到的较大值，由此就可以列出状态转移方程，dp[i][j]=max(dp[i+1][j]，dp[i+1][j+1])+f[i][j]。底层为边界，所以可以从最底层各位置的dp值开始，开始不断的网上求出每一层的dp值，然后一直走到最上边的时候，就得到了dp[1][1]。

最长回文子串问题，这个问题是说，给定一个字符串S，求这个最长回文子串的长度。题意很好理解，但是细节多。 可以令dp[i][j]表示S[i]到S[j]所表示的子串是否是回文子串，是就为1，不是就为0，状态转移情况就可以考虑到有两种情况，如果S[i]和S[j]相等的话，只要S[i+1]到S[j-1]时回文子串，那么S[i]到S[j]就是回文子串，否则就不是了，反之，如果S[i]和S[j]不相等的话，肯定不是回文子串。那么状态转移方程就可以写成dp[i][j]=dp[i+1][j-1]，当S[i]等于S[j]的时候；dp[i][j]=0，当S[i]不等于S[j]的时候。需要注意的是，为了确保状态可以转移，要从边界出发，按子串的长度和初始位置进行枚举，确保状态可以转移，按照这个思路就可以解决这个问题了。

最优三角形剖分问题，题意是说给定n个点的坐标，先问这些点是否能组成一个凸包，如果是凸包，用不相交的线来切这个凸包使得凸包只由三角形组成，根据cost(i，j)=|xi+xj|*|yi+yj|%p算切线的费用，问最少的切割费用。首先判断多边形是不是凸的，判断凸包的点数和给定的点数是不是一样多就可以了。然后就是最优三角形剖分，接下来要用n-3条直线将凸包切成n-2个三角形，然后具体实现的过程，可以先选择一个基准边，两端点标号为1和n，然后再选择一个点S，这样就在这个图形里边先形成了一个三角形，整个图形就被分成了3部分，然后中间这个新建立的三角形先不用管了，旁边两部分同样的方法进行分割，最后整个图形就被划分好了，全是由三角形组成，逐渐的将凸包分成一个个的子凸包并计算相应的费用，最后再更新到点1和点n为起始点的凸包就可以了。用Dp[i][j]表示以i为起点，j为终点的凸包被切割成一个个小三角形所需要的费用，列出状态转移方程为dp[i][j]=min(dp[i][k]+dp[k][j]+cost[i][k]+cost[k][j])求解就可以了。

核心部分代码：

int Graham(point *p,int n) {

	int i;
	sort(p,p + n,cmp);
	save[0] = p[0];
	save[1] = p[1];
	int top = 1;
	for(i = 0;i < n; i++){
 
		while(top && xmult(save[top],p[i],save[top-1]) >= 0)top--;
		save[++top] = p[i];
	}
 
	int mid = top;
	for(i = n - 2; i >= 0; i--){
 
		while(top>mid&&xmult(save[top],p[i],save[top-1])>=0)top--;
		save[++top]=p[i];
	}
	return top;
}
int Count(point a,point b) {
 
	return (abs(a.x + b.x) * abs(a.y+b.y)) % m;
}
 
 
int main()
{
	int i,j,k,r,u;

	while (scanf("%d%d",&n,&m) != EOF) {
		for (i = 0; i < n; ++i)
			scanf("%d%d",&p[i].x,&p[i].y);
		int tot = Graham(p,n);	
		if (tot < n) printf("I can't cut.\n");
		else 
			memset(cost,0,sizeof(cost));
			for (i = 0; i < n; ++i)
				for (j = i + 2; j < n; ++j)
					cost[i][j] = cost[j][i] = Count(save[i],save[j]);
	
			for (i = 0; i < n; ++i) {
		
				for (j = 0; j < n; ++j)
					dp[i][j] = INF;
				dp[i][(i+1)%n] = 0;
			}
			for (i = n - 3; i >= 0; --i)	
				for (j = i + 2; j < n; ++j) 
					for (k = i + 1; k <= j - 1; ++k)
						dp[i][j] = min(dp[i][j],dp[i][k]+dp[k][j]+cost[i][k]+cost[k][j]);
 
			printf("%d\n",dp[0][n-1]);
		}
	}
}

石子合并问题，这类题目题型有很多，其中一类就是说有N堆石子，现要将石子有序的合并成一堆，每次只能移动相邻的2堆石子合并，合并花费为新合成的一堆石子的数量，问将这N堆石子合并成一堆的总花费最小或者最大。这个题自己没大看懂，大体的解题方法就是用矩阵连乘的方式来解决，用dp[i][j]表示第i到第j堆石子合并的最优值，sum[i][j]表示第i到第j堆石子的总数量，列出状态转移方程，当i等于j的时候，dp[i][j]=0，当i不等于j的时候，dp[i][j]=min(dp[i][k]，dp[k+1][j])+sum[i][j]。然后这个题也有一个优化的思路，就是用平行四边形进行优化，枚举分割点的时候，就直接枚举p[i][j-1]到p[i+1][j]这个区间，而不用枚举[i，j]，降低复杂度。（参考题解）

优化代码如下：

int getMinval()
{
    for(int i=1; i<=n; i++)
    {
        dp[i][i] = 0;
        p[i][i] = i;
    }
    for(int len=1; len<n; len++)
    {
        for(int i=1; i+len<=n; i++)
        {
            int end = i+len;
            int tmp = INF;
            int k = 0;
            for(int j=p[i][end-1]; j<=p[i+1][end]; j++)
            {
                if(dp[i][j] + dp[j+1][end] + sum[end] - sum[i-1] < tmp)
                {
                    tmp = dp[i][j] + dp[j+1][end] + sum[end] - sum[i-1];
                    k = j;
                }
            }
            dp[i][end] = tmp;
            p[i][end] = k;
        }
    }
    return dp[1][n];
}

总结：

要用动态规划解决问题的话，必须拥有重叠子问题和最优子结构。

分治与动态规划相同之处在于，它们都是将问题分解为子问题，然后进行合并得到原问题的解。不同之处在于，分治的子问题没有重叠，动态规划有重叠子问题，而且分治解决的问题不一定最优，但是动态规划解决的问题一定是最优化问题。

再将贪心和动态规划比较一下吧。首先原来的问题一定要有最优子结构，贪心直接选择一个子问题求解，通过局部最优达到整体最优。动态规划会考虑所有子问题，选择最优结果，即使暂时没有被选择的子问题，后期也可能会再考虑，也有可能是最优解，所以最后一定得到最优解。

总体来说吧，虽然动态规划难，但是非常好用，用途广，得到的一定是最优解。设计好状态和写出状态转移方程是非常重要的，而且一些大佬的博客写的状态转移方程都非常长，但是还是得多理解呀，理解了那个过程，状态转移方程就理解得就相对容易一些了。

这学期acm的学习也快接近尾声了，在最后阶段更要坚持下去，不掉链子，保持良好的学习节奏，天气炎热更要沉心静气的去学习，继续认真的完成每一次任务！

下周继续努力！！！