动态规划
解题思路
确定 dp 数组以及下标的含义：dp[i] 表示 [0, i] 区间内以 nums[i] 结尾的最长递增子序列的长度；
确定递推公式：dp[i] = Math.max(dp[i], dp[j] + 1)
- 如果 nums[i] > nums[j] 则说明当前元素符合递增子序列，则 dp[i] = Math.max(dp[i], dp[j] + 1)；
- 如果 nums[i] < nums[j] 则说明当前元素不符合递增子序列，则什么都不做；
如何初始化 dp 数组：每一个 i，对应的 dp[i] （即最长递增子序列）起始大小至少都是 1；
确定遍历顺序：dp[i] 是有 [0, i-1] 各个位置的最长递增子序列 推导而来，那么遍历 i 一定是从前向后遍历；
举例推导 dp 数组：以 nums = [1, 3, 6, 7, 9, 4, 10, 5, 6] 为例：
j = 0 j = 1 j = 2 j = 3 j = 4 j = 5 j = 6 j = 7 j = 8 dp[0] 为区间 [0, 0] 之间递增子序列长度 1 1 1 1 1 1 1 1 1 dp[1] 为区间 [0, 1] 之间递增子序列长度 1 2 1 1 1 1 1 1 1 dp[2] 为区间 [0, 2] 之间递增子序列长度 1 2 3 1 1 1 1 1 1 dp[3] 为区间 [0, 3] 之间递增子序列长度 1 2 3 4 1 1 1 1 1 dp[4] 为区间 [0, 4] 之间递增子序列长度 1 2 3 4 5 1 1 1 1 dp[5] 为区间 [0, 5] 之间递增子序列长度 1 2 3 4 5 3 1 1 1 dp[6] 为区间 [0, 6] 之间递增子序列长度 1 2 3 4 5 3 61 1 dp[7] 为区间 [0, 7] 之间递增子序列长度 1 2 3 4 5 3 64 1 dp[8] 为区间 [0, 8] 之间递增子序列长度 1 2 3 4 5 3 64 5
复杂度
-
时间复杂度：
O(n^2)，遍历计算 dp 列表需O(N)，计算每个 dp[i] 需O(N)； -
空间复杂度：
O(n)；
代码实现
var lengthOfLIS = function (nums) {
let n = nums.length;
if (n === 0) return 0;
let dp = new Array(n).fill(1);
for (let i = 0; i < n; i++) {
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);
};
参考资料
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 309. 最佳买卖股票时机含冷冻期
上一篇
评论
