GingerBear
动态规划：堆积木
有n块积木，每块积木有体积vol和重量weight两个属性，用二元组(vol, weight)表示。积木需要搭成竖直的塔状，上面积木的体积和重量必须都比它下面的积木小。问最多可以搭多少个积木。
示例
有7个积木boxes:
[(65, 100), (70, 150), (56, 90), (75, 190), (60, 95), (68, 110), (80, 12)]
最多可以搭6个积木，从上到下分别为：
(56, 90), (60, 95), (65, 100), (68, 110), (70, 150), (75, 190)
所以函数应该返回6。
boilerplate
/*积木的定义(请不要在代码中定义该结构)
public class Box {
int vol, weight;
}*/
public class MaxBox {
public int maxBoxes(Box[] boxes) {
}
}
来源：http://www.itint5.com/oj/#34 || CRACKING THE CODING INTERVIEW 9.7
发出这一题的原因是，如果看了关于动态规划里的第一篇文章的初级部分，就可能会想出解这道题的思路。这题的做法是，先按照体积（vol）排序，然后重量（weight）的最长非降子序列的长度 (讲DP基本都会讲到的一个问题LIS：longest increasing subsequence)。
我看过了那篇讲LIS的文章，但依然还是感到疑惑它的**“状态”和“状态转移方程”**是怎么找出来的，难道没有每一个思路？只能靠灵感闪现嘛？
按照文章里说的，LIS的**“状态”d[i]就是，以arr[i]结尾的最大非降子序列的长度。比如[4, 12, 3, 23, 43, 2]，d[3]就是以23为结尾的最大非降子序列（LIS）为[12, 23]的长度，所以是2。“状态转移方程”，也就是d[i]跟前面的d的关系，是对于在第i个数之前的并且比它小**的数，在这些数中，以它们为结尾的LIS中最大的一个加上1，就等于以第i个数结尾的LIS，表达式即
for j < i && arr[j] < arr[i]
d[i] = max{1, d[j]} + 1
与1比较的原因是，arr[i]可能比之前所有的数都小，那么以arr[i]结尾的LIS就是它自己一个数了。
那么，为什么会想到把**"以arr[i]结尾的最大非降子序列的长度"作为状态呢？按照通常的思维（或者说我的第一反应），会把“到arr[i]为止最大的LIS”**作为状态。有人会说，以前者才能找到状态转移方程，后者无法得出方程。但这么说是建立在已经知道结果的情况下才说出来的。我还是没能想出一个合理的正向思考方法，在这里求解答。
我觉得这里说 "以arr[i]结尾的最大非降子序列” 而不是 “到arr[i]为止最大的LIS” 是因为这个array是没有排序的原因。如果排好序，那这两种说法就是一个意思了。 如果说在没有排序的情况下，你用"到arr[i]为止最大的LIS"作为状态，是无法构成状态转移方程的，例如 “1 3 5 2 7 8 10”：到5为止，d=3，但下一个是2，如果用"到...."的方法得出的d[2]仍为3，max{1,3}则还等于3，则意味着2的状态（即d[3]）为3，那么后面因为7比2大，则变成了max{1, 3+1}=4，这里就出错了。 不知道我说清楚没有。。另外neil你的方程写错了，是d[i] = max{1, d[j]+1}
