最长递增子序列长度动态规划
2024/01/26 15:07
题目
给定一个整数数组 nums ,找到其中最长严格递增子序列的长度。例如 [1, 2, 3]
的最长递增长度是 3
,[1, 7, 5, 6]
的最长递增子序列是 [1, 5, 6]
长度为 3
。
动态规划详解
完整代码
/**
* @param {number[]} nums
* @return {number}
*/
var lengthOfLIS = function (nums) {
const len = nums.length
if (len < 1) {
return len
}
const dp = new Array(len).fill(1)
for (let i = 1; i < len; i++) {
for (let j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
dp[i] = Math.max(dp[i], dp[j] + 1)
}
}
}
return Math.max(...dp)
}
详解步骤
数组长度小于
2
的不需要查找,例如[1]
[]
[5]
这些的长度只可能是0
或1
。
var lengthOfLIS = function (nums) {
const len = nums.length
if (len < 2) {
return len
}
// ...
}
创建一个和
nums
一样长度的数组,内部全部填充1
。
var lengthOfLIS = function (nums) {
// ...
const dp = new Array(len).fill(1)
// ...
}
其目的是存放 以当前数为结尾的递增子序列长度
nums = [1, 3, 5]
dp = [1, 1, 1] // 默认为 1
1
的递增子序列只可能为1
,长度也为1
3
的子序列为[1, 3]
, 长度为2
,5
的子序列为[1, 3, 5]
长度为3
。
最终 dp
内存储的子序列长度为:
dp = [1, 2, 3]
同理 [1, 7, 3, 5]
的 dp
数组就是 [1, 2, 2, 3]
。
双重遍历
nums
数组,在nums
里查找比当前数小的值。
var lengthOfLIS = function (nums) {
// ...
const dp = new Array(len).fill(1)
for (let i = 1; i < len; i++) {
for (let j = 0; j < i; j++) {
// 查找比 nums[i] 小的值
if (nums[j] < nums[i]) {
// ...
}
}
}
}
dp
数组中存储的是子序列长度,那么一旦查找到比当前数小的值,就可以获取到这个数在 dp
中存储的子序列长度。当前值比前面的值大,那前面的子序列肯定就归属于当前值。例如:
nums = [2, 3, 5]
// 初始 dp 为
dp = [1, 1, 1]
// 找到比 3 小的就是 2,那么 3 的子序列长度就是 (2 的子序列长度 + 1)即
dp[1] = dp[0] + 1 // dp = [1, 2, 1]
// 同理,比 5 小的有 2 和 3,先遍历到比 5 小的 2,那 dp 为
dp[2] = dp[0] + 1 // dp = [1, 2, 2]
// 再遍历到 3
dp[2] = dp[1] + 1 // dp = [1, 2, 3]
对应的代码就是
var lengthOfLIS = function (nums) {
// ...
const dp = new Array(len).fill(1)
for (let i = 1; i < len; i++) {
for (let j = 0; j < i; j++) {
// 查找比 nums[i] 小的值
if (nums[j] < nums[i]) {
// 查找到了就是 j 所存储的子序列长度 + 1
dp[i] = dp[j] + 1
}
}
}
}
但 nums
是乱序,可能会有 [2, 5, 6, 3, 8]
的情况,当遍历到 3
的时候,此时的 dp
数组是这样的
nums = [2, 5, 6, 3, 8]
dp = [1, 2, 3, 2, 1]
如果按照上面的代码逻辑,那么 8
所对应的子序列长度应该是
// nums[i] 为 8,nums[j] 为 3
dp[i] = dp[j] + 1
// dp 为 [1, 2, 3, 2, 3]
3
所对应的子序列很明显不是最长,所以需要和当前值的子序列长度进行比较,如果大于当前值的子序列长度,那么就更新,否则还是使用原长度。
var lengthOfLIS = function (nums) {
// ...
const dp = new Array(len).fill(1)
for (let i = 1; i < len; i++) {
for (let j = 0; j < i; j++) {
// 查找比 nums[i] 小的值
if (nums[j] < nums[i]) {
// 和当前存储的子序列长度进行比较,取最大值
dp[i] = Math.max(dp[j] + 1, dp[i])
}
}
}
}
最后返回 dp
数组中的最大值即可。
var lengthOfLIS = function (nums) {
// ...
const dp = new Array(len).fill(1)
for (let i = 1; i < len; i++) {
for (let j = 0; j < i; j++) {
// 查找比 nums[i] 小的值
if (nums[j] < nums[i]) {
// 和当前存储的子序列长度进行比较,取最大值
dp[i] = Math.max(dp[j] + 1, dp[i])
}
}
}
return Math.max(...dp)
}