好久没有更新技术文章了，再一次希望能通过文章记录自己的想法。同时把思想和理解分享给大家 。帮助遇到同样问题的人一起理解，多好的一件事。
这次文章主要将ccf的一道题，自己在做的过程中。不用多说就是一脸懵逼。自己的算法真的菜成渣。我自己都不忍直视，我想说我对自己的算法能力要求不高，但渣成这样就有点看不过去了。基本10道题8道不会2道能对一部分，想自己写全对一道题，比登天还难。
好了 ，言归正传。
题目：
试题编号： 201612-4
试题名称： 压缩编码
时间限制： 3.0s
内存限制： 256.0MB
问题描述：
问题描述
给定一段文字，已知单词a1, a2, …, an出现的频率分别t1, t2, …, tn。可以用01串给这些单词编码，即将每个单词与一个01串对应，使得任何一个单词的编码（对应的01串）不是另一个单词编码的前缀，这种编码称为前缀码。
使用前缀码编码一段文字是指将这段文字中的每个单词依次对应到其编码。一段文字经过前缀编码后的长度为：
L=a1的编码长度×t1+a2的编码长度×t2+…+ an的编码长度×tn。
定义一个前缀编码为字典序编码，指对于1 ≤ i < n，ai的编码（对应的01串）的字典序在ai+1编码之前，即a1, a2, …, an的编码是按字典序升序排列的。
例如，文字E A E C D E B C C E C B D B E中， 5个单词A、B、C、D、E出现的频率分别为1, 3, 4, 2, 5，则一种可行的编码方案是A:000, B:001, C:01, D:10, E:11，对应的编码后的01串为1100011011011001010111010011000111，对应的长度L为3×1+3×3+2×4+2×2+2×5=34。
在这个例子中，如果使用哈夫曼(Huffman)编码，对应的编码方案是A:000, B:01, C:10, D:001, E:11，虽然最终文字编码后的总长度只有33，但是这个编码不满足字典序编码的性质，比如C的编码的字典序不在D的编码之前。
在这个例子中，有些人可能会想的另一个字典序编码是A:000, B:001, C:010, D:011, E:1，编码后的文字长度为35。
请找出一个字典序编码，使得文字经过编码后的长度L最小。在输出时，你只需要输出最小的长度L，而不需要输出具体的方案。在上面的例子中，最小的长度L为34。
输入格式
输入的第一行包含一个整数n，表示单词的数量。
第二行包含n个整数，用空格分隔，分别表示a1, a2, …, an出现的频率，即t1, t2, …, tn。请注意a1, a2, …, an具体是什么单词并不影响本题的解，所以没有输入a1, a2, …, an。
输出格式
输出一个整数，表示文字经过编码后的长度L的最小值。
样例输入
5
1 3 4 2 5
样例输出
34
样例说明
这个样例就是问题描述中的例子。如果你得到了35，说明你算得有问题，请自行检查自己的算法而不要怀疑是样例输出写错了。
评测用例规模与约定
对于30%的评测用例，1 ≤ n ≤ 10，1 ≤ ti ≤ 20；
对于60%的评测用例，1 ≤ n ≤ 100，1 ≤ ti ≤ 100；
对于100%的评测用例，1 ≤ n ≤ 1000，1 ≤ ti ≤ 10000。
这道题的解题思路是来自一个叫做石子合并问题。
因为要保证原始的字典顺序，所以要两两合并只能是相邻的单词进行合并。那么如何选择就是石子问题里面的方法可以解决。用到区间dp。
设dp[i][j]表示第i到第j堆石子合并的最优值，sum[i][j]表示第i到第j堆石子的总数量。那么就有状态转移公式：
1、dp[i][j]=0 (i==j)
2、dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[i][j]) (i!=j)
此时算法复杂为O(n^3)。
其中k是刚好取得最小值的那个合适的k值 。
解题代码：
public static int minCost(int[] A) {
int n = A.length;
int[][] f = new int[n][n];
int[] sum = new int[n];
for(int i=0; i<n; i++) {
sum[i] = (i>0?sum[i-1]:0) + A[i];
}
for(int i=0; i<n; i++) {
Arrays.fill(f[i], Integer.MAX_VALUE);
f[i][i] = 0;
}
for(int w=2; w<=n; w++) { // sliding window size
for(int i=0; i<=n-w; i++) { // window start position
int j = i+w-1; // window end position
int sumij = sum[j] - (i>0?sum[i-1]:0);
for(int k=i; k<j; k++) {
f[i][j] = Math.min(f[i][j], f[i][k] + f[k+1][j] + sumij);
}
}
}
return f[0][n-1];
}
具体的程序的过程是这样的：
首先我们完成一些初始化的工作 ，比如赋值sum数组。然后二维的f数组(就是dp[][]) 同时把对角线上的值赋值为0 因为自己不能和自己合并 那么花费的值即为0.
然后到了最重要的for循环，单独贴一下代码：
for(int w=2; w<=n; w++) { // sliding window size
for(int i=0; i<=n-w; i++) { // window start position
int j = i+w-1; // window end position
int sumij = sum[j] - (i>0?sum[i-1]:0);
for(int k=i; k<j; k++) {
f[i][j] = Math.min(f[i][j], f[i][k] + f[k+1][j] + sumij);
}
}
}
这段代码的意思是首先确定一个i和j的区间大小w，然后在这个区间上去枚举可能的情况，之后把最小的值保存下来。比如，当w=2时 那么i和j就是相邻的两个数，那么它们合并的最小值就是它们本身合并，然后把整个数组都依次俩俩合并。保存到f中。
就拿测试用例来作为例子：
上面就是w=2时的直观过程 ，此时的决策只有一种可以选择。就是相邻的合并
下面再例举一下w=3，那么此时i和j之间一共3个元素，i=0 j=2。此时i和j之间有2种决策可以选择。
3和4合并然后和1合并 这个时候的dp[i][j]=3+4+8=15
1和3合并 然后和4合并 dp[i][j]=1+3+8=12
自然旋转第二种的情况 ，依赖于w=2时的结果 这样遍历一次就把w=3的情况都记录下来了。那么依次类推。会有w=4等。
那么w=n就会有n-1种决策，这些决策依赖于之间的局部最优解。也就是区间DP了。
那么还有一个叫做平行四边形的优化，
可以利用平行四边形优化降为O(n^2)：
由上面的方程式可知我们每次求dp[i][j]的关键是找到合适的k值，设p[i][j]为dp[i][j]的这个合适的k值，根据平行四边形规则有以下不等式：p[i][j-1]<=p[i][j]<=p[i+1][j]。
那么求解dp[i]i+L的复杂度就为：
(p[2,L+1]-p[1,L])+(p[3,L+2]-p[2,L+1])…+(p[n-L+1,n]-p[n-L,n-1])=p[n-L+1,n]-p[1,L]≤n。
复杂度为O(n)。然后L从1循环至n，总复杂度就为O(n^2)。
对于这个不等式我不是特别了解和明白这个证明过程，它的适用条件也是要出现类似dp[i][j]=min(dp[i][k],dp[k+1][j]) 然后k就不用从头开始遍历 而是从p[i][j-1]开始到p[i+1][j]。
附上C++的代码：
#include <iostream>
#include <cstring>
using namespace std;
const int INT_MAX2 = 0x7F7F7F7F;//并不是整数的最大值 只是将就的做法
const int N = 1000;
int v[N+1];
int sum[N+1]; //sum[i] 代表从第0堆到i堆的石子数量和
int dp[N+1][N+1]; //dp[i][j] 代表第i堆石子到第j堆石子合并的最优值
int p[N+1][N+1]; //p[i][j] 代表dp[i][j] 合适的k值
//合适的k值 使得 合并的顺序得到最优解
int main()
{
int n;
// 变量初始化：置为最大值
memset(dp, INT_MAX2, sizeof(dp));
// 输入数据
cin >> n;
sum[0] = 0;
for(int i=1; i<=n; i++) {
cin >> v[i];
sum[i] = sum[i-1] + v[i];
dp[i][i] = 0; //自己和自己合并 0 因为自己不能和自己合并
p[i][i] = i; //合适的k 为 i
}
// DP计算 这里有点类似 滑动窗口的感觉
for(int len=2; len<=n; len++) // i 和j之间的区间大小 len
for(int i=1; i+len-1<=n; i++) {
int j = i + len - 1;
//平行四边形等式优化
//根据平行四边形规则有以下不等式：p[i][j-1]<=p[i][j]<=p[i+1][j]
//原本遍历寻找k值 是从i开始到j 现在只需要缩小到从p[i][j-1] 到 p[i+1][j]
for(int k=p[i][j-1]; k<=p[i+1][j]; k++) {
int val = dp[i][k] + dp[k+1][j] + sum[j] - sum[i-1];//计算合并的花费
if(dp[i][j]>val) { //保存最小值
dp[i][j] = val;
p[i][j] = k; //记录取得最小值时候的k值
}
}
}
// 输出结果
cout << dp[1][n] << endl;
return 0;
}
