NEEDREVIEWDDP

300. Longest Increasing Subseque

2017-04-07  本文已影响18人  DrunkPian0

https://www.youtube.com/watch?v=CE2b_-XfVDk&t=300s

07/04/2017更新

今天又仔细写了一遍,发现这题昨天还是没想清楚。
昨天我以为, if (nums[i] > nums[j]) 这句决定了dp里面有些位是0的,其实不是的,这个if只是会更新max的值,如果不更新,那dp这一位就等于之前的max的,也正因为如此,max是要在外层for每次右移都更新的。另外也正因为如此,最后返回的结果不能是dp[nums.length-1]。


debug

另外,看了一下第二种方法,二分+一个for循环,但感觉有点tricky,不太好找规律。偷懒了,不写了。

以下讲解摘自:http://www.jianshu.com/p/a3cd9df6d9d1

这种方法的解题步骤是:
-将第1个数字加入解集;
-依次读取后面的数字,如果此数字比解集中最后一个数字大,则将此数字追加到解集后,否则,用这个数字替换解集中第一个比此数字大的数,解集是有序的,因此查找可以用二分法,复杂度O(log n);
-最后的答案是解集的长度(而解集中保存的并不一定是合法解)。
举个栗子,输入为[1,4,6,2,3,5]:
-解集初始化为[1];
-读到4,将其追加到解集中,解集变为[1,4];
-读到6,将其追加到解集中,解集变为[1,4,6];
-读到2,用其替换解集中的4,解集变为[1,2,6],注意此时解集不是一个合法解,因为2是在6后出现的,但是解集的长度始终标识着当前最长序列的长度;
-读到3,用其替换解集中的6,解集变为[1,2,3];
-读到5,将其追加到解集中,解集变为[1,2,3,5],得到答案为解集长度4。


06/04/2017

LIS问题,老生常谈的一维DP问题了。但是我这题竟然想了很久没想通。最后还看了答案调试了一会儿。有时感觉一维dp比二维dp还要复杂。。或者说因为我脑子现在已经不转了。。好累。这两天好累啊,白天上班晚上上课,尤其上完课大半夜再想这个,脑子已经不怎么转了,很痛苦。我不喜欢这种节奏。很烦。

还有O(nlogn)的方法,抽空再看了。。

    public int lengthOfLIS(int[] nums) {
        if (nums.length == 0) return 0;
        int dp[] = new int[nums.length];
        dp[0] = 1;
        int res = 1;
        for (int i = 1; i < nums.length; i++) {
            //max不能是全局的
            int max = 1;
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    //这里不能就开始改变dp[i],否则下一次循环就乱了
                    max = Math.max(dp[j] + 1, max);
                }
            }

            dp[i] = max;

            res = Math.max(dp[i] , res);

        }
        return res;
    }
上一篇下一篇

猜你喜欢

热点阅读