动态规划（四边形不等式优化）

区间型动态规划：合并石子

状态转移方程：

显而易见，这种方法时间复杂度是O(n^3)，如何去优化？

四边形不等式

通过四边形不等式的优化，可以进一步限定k的范围，从而可以将事件复杂度降为 O(n^2)，我们最终的目的是证明决策变量k的单调性。

通过不断的搜索，发现此优化方法原来是姚期智的夫人储枫(Frances Yao)所写，默默 膜拜了一番。

算法相关论文地址：论文

价值函数c[i,j]

公式1：

满足公式1，说明价值函数c[i,j]满足区间的单调性。

公式2：

满足公式2，说明价值函数c[i,j]满足四边形不等式。

对于石子合并问题，价值函数显然满足上述两个公式。

状态转移函数m[i,j]

要证明状态转移函数也满足四变形不等式.

引理1:

具体的证明过程是通过数学归纳法来的，相关证明过程可参看论文，本人愚顿，看了 好久，才感觉明白了，最重要的一步则是： 证明的过程中又引用了需要证明的结论，我的理解是数学归纳法，上述公式的范围 比结论的范围小，故可以引用。

决策变量的单调性

假设k[i,j]表示m[i,j]取得最小值时的决策值。

引理2： 根据对称性只需证明k[i,j-1]<=k[i,j], 假设x=k[i,j-1]，对任意i<y<x<j-1<j.

不等式两侧同时加上：

then:

因为：

所以:

从而可以确定k[i,j]不可能小于x，也就是说k[i,j-1]<=k[i,j].

石子合并代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int piles[5001];

int *status[5001];
int *cv[5001];

void quard_dp(){
	int n, i, j, k, dis;
	int min ,tmp;
	scanf("%d", &n);
	piles[0] = 0;
	while(n != 0) {
		for(i = 1; i <= n; i++){
			scanf("%d", &piles[i]);
			piles[i] += piles[i-1];
			status[i] = (int*)malloc((n+1) * sizeof(int));
			status[i][i] = 0;
			cv[i] = (int*)malloc((n+1) * sizeof(int));
			cv[i][i] = i;
		}

		for(dis = 1; dis < n; ++dis){
			for(i = 1; i <= n-dis; i++){
				j = i + dis;
				min = INT_MAX;
				for(k = cv[i][j-1]; k <= cv[i+1][j] && k < n; ++k){
					tmp = status[i][k] + status[k+1][j] + piles[j]- piles[i-1];
					if(tmp < min) {
						min = tmp;
						cv[i][j] = k;
					}
				}
				status[i][j] = min;
			}
		}
		printf("%d\n", status[1][n]);
		for(i = 0; i < n; i++){
			free(status[i]);
			free(cv[i]);
		}

		scanf("%d", &n);
	}
}