这个问题可以只使用一个 dp 数组来完成吗？
这是来自 topcoder ( http://community.topcoder.com/stat?c=problem_statement&pm=1259&rd=4493 ) 的锯齿问题
如果连续数字之间的差异在正负之间严格交替，则一个数字序列称为之字形序列。第一个差异(如果存在)可能是正的也可能是负的。少于两个元素的序列通常是锯齿形序列。
例如，1,7,4,9,2,5 是一个锯齿形序列，因为差异 (6,-3,5,-7,3) 是交替的正负。相比之下，1,4,7,2,5 和 1,7,4,5,5 不是锯齿形序列，第一个是因为它的前两个差是正的，第二个是因为它的最后一个差为零。
给定一个整数序列，sequence，返回作为锯齿形序列的序列的最长子序列的长度。子序列是通过从原始序列中删除一定数量的元素(可能为零)而获得的，保留其余元素的原始顺序。
最佳答案
供引用:具有两个数组的 DP 使用数组 A[1..n]，其中 A[i] 是以元素 i 上的 zig 结尾的之字形序列的最大长度，以及数组 B[1..n] ] 其中 B[i] 是以元素 i 上的 zag 结尾的 zig-zag 序列的最大长度。对于从 1 到 n 的 i，此 DP 使用 A 数组的先前条目来计算 B[i]，并使用 B 数组的先前条目来计算 A[i]。以额外循环为代价，可以按需重新创建 B 条目，从而仅使用 A 数组。不过，我不确定这是否能解决您的问题。
(另外，由于输入数组太短，有许多编码技巧不值得一提。)
关于algorithm - 动态规划 : Find longest subsequence that is zig zag using only one dp array，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/21937917/