最长递增子序列，动态编程 [英] Longest Increasing Subsequence, Dynamic Programing

问题描述

我有以下问题：

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

Find the longest increasing subsequence of a given sequence / array.

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

In other words, find a subsequence of array in which the subsequence’s elements are in strictly increasing order, and in which the subsequence is as long as possible. This subsequence is not necessarily contiguous, or unique. In this case, we only care about the length of the longest increasing subsequence.

示例：

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

Input : [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15] Output : 6 The sequence : [0, 2, 6, 9, 13, 15] or [0, 4, 6, 9, 11, 15] or [0, 4, 6, 9, 13, 15]

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

This is a DP problem and I do have some issue at the memorization step. Here is my code:

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;
}

如果没有HashMap备忘录，我不确定结果是否正确为什么这样做会给我错误的结果？

Without the memo HashMap in place I have the correct result, I am not sure why this is giving me the wrong result once in place.

谢谢。

推荐答案

这是因为您没有照顾 lastElt 。基本上，根据 lastElt 的值，给定的 index 可以有多个解决方案。因此，您必须为备忘录的密钥包含两个索引和 lastElt 。

That is because you are not taking care of the lastElt. Basically, you can have more than one solution for a given index depending on what was the lastElt value. Therefore, you would have to have a Key for your memo that contains both index and 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;
    }

这篇关于最长递增子序列，动态编程的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！