Buy one get one free - Zenefits

http://yuancrackcode.com/2015/10/23/buy-one-get-one-free/
一堆商品，买一个可以送一个，但送的那个的价格必须小于买的那个的价格（强调一下，不能等于）。给定商品总数n和每个商品的价格，求得到全部商品的最少开销。 例如：4个商品价格为[5, 4, 3, 3]，最优解为9，即买5和4，送3和3。 
两个test case: [100, 99, 98, 1, 1, 1], [100, 99, 98, 98, 97, 97, 97, 97]
http://www.jiuzhang.com/qa/221/

这个题确实是很难的动态规划。属于区间型动态规划。在九章算法强化班中会讲到这个类型的动态规划。

首先排序不用说了。从小到大（从大到小也可以，我比较喜欢从小到大）。然后先给出DP的方程：

定义状态 f[i][j] 为 i 到 j 这一段的最优值（最少花多少钱全买下来）
    f[i][j] = min(f[i + 1][j - 1]+A[j], f[i][k] + f[k+1][j]) 其中k为i到j-1。

然后我们来证明为什么这个方程是对的。这个方程的假设前提是，不存在相交的搭配，也就是说不存在下面这种情况的匹配：

从小到大的4个数：a<= b<= c<= d。 a与c一起买，b与d一起买。

为毛呢？首先a和d肯定不相等，否则的话，abcd都相等了，这种情况是不会出现的（我们就是要证明这种情况不会出现），然后看b和c，如果他们相等，那么换成(a,b)和(c,d)，代价一样，并且不会产生相交的匹配（什么叫做相交？你在ac连一条曲线，和bd之间的曲线一定相交）。然后看b和c不等的情况，不等的话，换成(b,c) + (a,d)，也还是不影响结果=c+d， 然后又能使得连线不相交。

好了，上面我们证明了不相交理论。那么既然连线不想交的话，i-j这一段的匹配情况，只存在两种可能性：

• 第一种可能是i和j匹配，然后中间的自己配对。
• 第二种可能是，一定存在一条分割线，使得这个i-j的区间被分为i-k和k+1-j，两个区间之间的自己匹配，没有互相的连边。

好了，综上所述。问题已经解决并证明。我知道理解起来有点难，特别是证明，我也证明了好久……

顺便说一下时间复杂度 ： O(n^3)，可能可以用决策单调的优化优化到O(n^2)。

你可能要问我，我TMD是怎么想到这个解法的呢？因为课上讲过的DP就那么几种大类型……面试99%都落在 “划分/区间/矩阵/双序列/背包" 这五种类型。一个个试试看就行了……首先想到的是划分，然后发现推导不出来。然后矩阵肯定不是，双序列和背包也不是，只剩下区间了……

http://www.1point3acres.com/bbs/thread-143891-1-1.html
http://www.1point3acres.com/bbs/thread-143891-2-1.html

1. int LeastCost(vector<int>& costs) {
2.         int n = costs.size();. 1point 3acres 璁哄潧
3.         if (n == 0)
4.                 return 0;
5.         sort(costs.begin(), costs.end());
6.         vector<vector<int> > T(n, vector<int>(n, 0));. 涓€浜�-涓夊垎-鍦帮紝鐙鍙戝竷
7. 
   
8.         for (int i = 0; i < n; i++)
9.                 T[i][i] = costs[i];
10.         for (int len = 2; len <= n; len++)
11.                 for (int i = 0, j = i + len - 1; j < n; i++, j++) {. 鍥磋鎴戜滑@1point 3 acres
12.                         T[i][j] = T[i][j-1] + costs[j];
13.                         for (int k = i; k < j; k++) {
14.                                 int p1 = costs[j], p2 = 0, p3 = 0;
15.                                 if (costs[k] == costs[j])
16.                                         p1 += costs[k];
17.                                 if (k - 1 >= i)
18.                                         p2 = T[i][k-1];
19.                                 if (j - 1 >= k + 1). 鐗涗汉浜戦泦,涓€浜╀笁鍒嗗湴
20.                                         p3 = T[k+1][j-1];
21.                                 if (p1 + p2 + p3 < T[i][j])
22.                                         T[i][j] = p1 + p2 + p3;
23.                         }
24.                 }
25.         return T[0][n - 1];
26. }