讨论/《中级算法》 - 最长上升子序列/
《中级算法》 - 最长上升子序列
共 5 个回复

根据经验,尝试参考最大回文子串长度那道题,设dp[i][j]为从 i 到 j 的最大严格递增子序列的长度,但规律不明显,遂放弃。

多次尝试后,设dp[i]为索引 i 到字符串末尾的最大严格递增子序列的长度,对于输入[0,1,0,3,2,3],枚举子问题的解大致过程如下:

// nums[2] === nums[0],所以不可以选择dp[2]
dp[0] = Math.max(dp[1], dp[3], dp[4], dp[5], 0) + 1 = 4;

// nums[2] < nums[1],所以不可以选择dp[2]
dp[1] = Math.max(dp[3], dp[4], dp[5], 0) + 1 = 3;

// 所有子问题的解都可以选择
dp[2] = Math.max(dp[3], dp[4], dp[5], 0) + 1 = 3;

// nums[4] < nums[3],nums[5] = nums[3],所以都不可以选择
dp[3] = Math.max(0) + 1 = 1;

dp[4] = Math.max(dp[5], 0) + 1 = 2;

dp[5] = Math.max(0) + 1 = 1;

发现dp[i]就是在所有子问题dp[i - 1],dp[i - 2],...,dp[dp.length - 1]的解中做选择,选择长度最大的一个解max,且此时隐含的意思就是已经选定了nums[i],所以dp[i] = max + 1;特别的,一个可以被选择的子问题的解,其序列的最小值(即该子序列首项)一定要大于nums[i];另外发现这样做假设的话,所求的当前项dp[i]依赖于所有索引比 i 大的项,所以填充解空间dp时要从index = dp.length - 1开始遍历,每次迭代 i 减一。

状态转移方程(对于dp[i]的每个子问题解dp[j],必须符合nums[i] < nums[j] && i < j < nums.length):dp[i] = Math.max(0, dp[j]) + 1;

TS 实现如下:

function lengthOfLIS(nums: number[]): number {
    const dp = new Array(nums.length);
    let result = 1;
    dp[dp.length - 1] = 1;
    for (let i = dp.length - 2; i > -1; i--) {
        let max = 0;
        for (let j = i + 1; j < dp.length; j++) {
            if (nums[i] < nums[j]) {
                max = Math.max(max, dp[j]);
            }
        }
        dp[i] = max + 1;
        result = Math.max(result, dp[i]);
    }
    // console.log(dp);
    return result;
};

与官方题解求解顺序刚好相反,神奇的脑回路。。。

3

执行用时:296 ms, 在所有 C++ 提交中击败了60.23% 的用户
内存消耗:10 MB, 在所有 C++ 提交中击败了94.92% 的用户

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) 
    {
        int dp[2501]={1};
        int max=0;
        for(int i=0;i<nums.size();i++)
        {
            dp[i]=1;
            for(int j=0;j<i;j++)
            {
                if(nums[i]>nums[j]&&dp[i]<dp[j]+1) dp[i]=dp[j]+1;   
            }
            if(dp[i]>max) max=dp[i];
        }
        return max;
    }
};
1
/*
根据官方题解,这里动态转移方程是:
    dp[i]=max(dp[j])+1,其中0≤j<i且num[j]<num[i]
官方意思就是  (以示例2为例)
    用一个dp数组保存 以nums数组当前索引位置的元素为末尾的最长的递增子序列的长度
    dp[0] = 1  //一个数就是一个子序列的长度1  最长子序列:[0]
    dp[1] = max(dp[0]+1 = 2, 前面所有元素中比当前元素的小的最大dp值  [0,1]
    dp[2] = max(没有==0)+1 = 1,没有比0小的,所以直接是1     [0]
    dp[3] = max(dp[0],dp[1],d[2])+1 = 3,通过nums数组得有0,1,2位置的元素小于当前,找最大子序列长度来+1  [0,1,3]
    dp[4] = max(dp[0],dp[1],dp[2])+1 = 3 ......  [0,1,2]
    dp[5] = max(dp[0],dp[1],dp[2],dp[4])+1 = 4  ......  [0,1,2,3]

    所以得到dp数组为[1,2,1,3,3,4]
    依次对应着nums数组索引位置元素为末尾的最长递增子序列的长度
    然后找到其中最大值即可。
*/
class Solution {
    public int lengthOfLIS(int[] nums) {
        int len = nums.length;
        int[] dp = new int[len];
        dp[0] = 1;
        int res = 1;
        for(int i = 1;i<len;i++){
            int max = Integer.MIN_VALUE;
            for(int j = 0;j<i;j++){
                if(nums[j]<nums[i] && dp[j]>max){
                    max = dp[j];
                }
            }
            dp[i] = max == Integer.MIN_VALUE ? 1 : max+1;
            res = Math.max(res,dp[i]);
        }
        return res;
    }
}

java实现代码

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] f = new int[n];     // f[i]表示以下标i结尾的最长上升子序列(Lis)
        f[0]=1;

        for(int i=1;i<n;i++){
            f[i]=1;
            for(int j=0;j<i;j++){
                if(nums[i]>nums[j]){
                    f[i]=Math.max(f[j]+1,f[i]);
                }
            }
        }
        Arrays.sort(f);
        return f[f.length-1];
    }
}

这个用python不能用记忆法,只能制表,记忆法超时