最长的子序列，动态编程

我有以下问题：

找到给定序列/数组的增长最长的子序列。

换句话说，找到数组的子序列，其中子序列的元素严格按顺序递增，并且子序列尽可能长。 该子序列不一定是连续的或唯一的。 在这种情况下，我们只关心最长的增长子序列的长度。

示例：

输入：[0,8,4,12,2,10,6,14,1,9,5,13,​​3,11,7,15]输出：6序列：[0,2,6,9， 13,15]或[0,4,6,9,11,15]或[0,4,6,9,13,15]

这是一个DP问题，我在记忆步骤中确实遇到了一些问题。 这是我的代码：

public int lis(final List a) { return maxIncreasing(0, Integer.MIN_VALUE, a); } HashMap memo = new HashMap(); private int maxIncreasing(int index, int lastElt, final List a) { if(memo.containsKey(index)) return memo.get(index); // end? if(index >= a.size()) return 0; int weTake = Integer.MIN_VALUE; // can we take it? if(a.get(index) > lastElt) { // take it or don't weTake = maxIncreasing(index + 1, a.get(index), a) + 1; } int weDoNot = maxIncreasing(index + 1, lastElt, a); int max = Math.max(weTake, weDoNot); memo.put(index, max); return max; } 

如果没有备忘录HashMap，我会得到正确的结果，我不知道为什么这会给我一个错误的结果。

谢谢。

Answer 1

那是因为你没有照顾到lastElt 。 基本上，您可以为给定index提供多个解决方案，具体取决于lastElt值。 因此，您必须拥有包含index和lastElt memo的Key 。

你可以这样做：

  class Key { final int index; final int lastEl; Key(int index, int lastEl) { this.index = index; this.lastEl = lastEl; } @Override public boolean equals(Object o) { if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; Key key = (Key) o; if (index != key.index) return false; return lastEl == key.lastEl; } @Override public int hashCode() { int result = index; result = 31 * result + lastEl; return result; } } public int lis(final List a) { return maxIncreasing(0, Integer.MIN_VALUE, a); } HashMap memo = new HashMap<>(); private int maxIncreasing(int index, int lastElt, final List a) { Key key = new Key(index ,lastElt); if(memo.containsKey(key)) return memo.get(key); // end? if(index >= a.size()) return 0; int weTake = Integer.MIN_VALUE; // can we take it? if(a.get(index) > lastElt) { // take it or don't weTake = maxIncreasing(index + 1, a.get(index), a) + 1; } int weDoNot = maxIncreasing(index + 1, lastElt, a); int max = Math.max(weTake, weDoNot); memo.put(key, max); return max; }