最长增子序列动态规划

Question

我有以下问题：

示例：

输入:[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,11,15]

这是一个DP问题，我确实有一些问题在记忆步骤。下面是我的代码：

public int lis(final List<Integer> a) {
    return maxIncreasing(0, Integer.MIN_VALUE, a);
}
HashMap<Integer, Integer> memo = new HashMap<>();
private int maxIncreasing(int index, int lastElt, final List<Integer> 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;
}

多谢了。

Answer 1

这是因为您没有处理lastelt。基本上，对于给定的index可以有多个解决方案，具体取决于lastelt值。因此，您的备忘录必须有一个包含索引和Lastelt的键。

你可以这样做：

    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<Integer> a) {
        return maxIncreasing(0, Integer.MIN_VALUE, a);
    }
    HashMap<Key, Integer> memo = new HashMap<>();
    private int maxIncreasing(int index, int lastElt, final List<Integer> 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;
    }