leetcode.300【Js】

朱雀 2022-08-29 13:51 96阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0Nsb3VkMTIwOQ_size_16_color_FFFFFF_t_70]

**dp\[i\]的定义：**  
`dp[i]表示i之前包括i的最长上升子序列。`

**状态转移方程**  
`位置i的最长升序子序列等于j从0到i-1各个位置的最长升序子序列 + 1 的最大值。`

`if (nums[i] > nums[j]){`  
`dp[i] = max(dp[i], dp[j] + 1);`  
`}`

*注意这里不是要dp\[i\] 与 dp\[j\] + 1进行比较，而是我们要取dp\[j\] + 1的最大值。*

**dp\[i\]的初始化**  
`每一个i，对应的dp[i]（即最长上升子序列）起始大小至少都是是1.`

**确定遍历顺序**  
`dp[i] 是有0到i-1各个位置的最长升序子序列 推导而来，那么遍历i一定是从前向后遍历。`

`j其实就是0到i-1，遍历i的循环里外层，遍历j则在内层`

/** * @param {number[]} nums * @return {number} */
    var lengthOfLIS = function(nums) { 
        let dp=[1];
        for(let i=1;i<nums.length;i++){ 
            dp[i]=1;
            for(let j=0;j<i;j++){ 
                if(nums[i]>nums[j]){ 
                    dp[i]=Math.max(dp[i],dp[j]+1);
                }
            }
        }
            return Math.max(...dp);
    };

时间复杂度：O(n2)。  
空间复杂度：O(n)

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0Nsb3VkMTIwOQ_size_16_color_FFFFFF_t_70]: /images/20220829/fa5a87d3407e42fc9807583de8c6fc63.png

发表评论取消回复

表情：

评论列表（有 0 条评论，96人围观）

还没有评论，来说两句吧...

相关阅读

相关 leetcode300 最长上升子序列

经典题，不解释，可以看我之前文章。普通dp public class Solution { public int lengthOfLIS(in

系统管理员/ 2023年06月16日 10:35/ 0 赞/ 189 阅读

相关 leetcode 300-400

文章目录重做题目 300，301，306，307，309，310,312,313,315,316，318,321，322，324,329,330,331，332,

骑猪看日落/ 2023年03月13日 03:41/ 0 赞/ 22 阅读

相关 leetcode 200-300

文章目录重做题 200. 岛屿数量 201. 数字范围按位与 202. 快乐数 203. 移除链表元素 204. 计数质数 2

本是古典何须时尚/ 2023年02月10日 05:19/ 0 赞/ 25 阅读

相关 LeetCode 300. 最长递增子序列

[LeetCode 300. 最长递增子序列][LeetCode 300.] Idea 最长递增子序列，首先就想到了LCS（最长公共子序列），这个其实比最长公共子序列还

淩亂°似流年/ 2023年01月23日 07:59/ 0 赞/ 235 阅读

相关 leetcode300. 最长递增子序列

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bmy5ZWl5ZWl5

曾经终败给现在/ 2022年09月12日 05:52/ 0 赞/ 227 阅读

相关 leetcode.300【Js】

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

朱雀/ 2022年08月29日 13:51/ 0 赞/ 97 阅读

相关 LeetCode300——Longest Increasing Subsequence

LeetCode300——Longest Increasing Subsequence 题意：最长上升子串，LIS问题，经典的动态规划问题。据说有用到二分的方法，这个还没

青旅半醒/ 2022年08月09日 19:30/ 0 赞/ 82 阅读

相关 leetcode 300. Longest Increasing Subsequence

Given an unsorted array of integers, find the length of longest increasing subsequence.

今天药忘吃喽~/ 2022年07月28日 01:20/ 0 赞/ 185 阅读

相关 LeetCode300最长上升子序列

给定一个无序的整数数组，找到其中最长上升子序列的长度。示例: 输入: \[10,9,2,5,3,7,101,18\] 输出: 4 解释: 最长的上升子序列是 \[

比眉伴天荒/ 2022年01月05日 04:43/ 0 赞/ 276 阅读

相关 leetcode[300] 最长上升子序列

给定一个无序的整数数组，找到其中最长上升子序列的长度。示例: 输入: \[10,9,2,5,3,7,101,18\] 输出: 4 解释: 最长的上升子序列是 \

刺骨的言语ヽ痛彻心扉/ 2021年10月03日 02:34/ 0 赞/ 308 阅读