题目描述
给定一个仅含数字的数组，查找严格递增子序列的长度。
比如：[5, 7, -24,12,13,2,3,12,5,6,35]
最长子序列长度是6，即[-24, 2, 3, 5, 6, 35]
方法一：递归查找
这个题的难点在于，不能一味地取比前一个值大的数，这样得不到最优解，所以，对于比前一个值大的数，需要考察取或不取2种情况。
在递归查找时，对于比前一个数小的数，直接考察下一个位置，路径不变。比前一个数大的数，需要递归2次，取当前位置和不取当前位置，取最长的路径。
代码实现：
var lengthOfLIS = function(nums) {
return recursive(0, -Infinity)
function recursive(pos, value) {
// 边界处理
if(pos >= nums.length) return 0
let path1 = 0, path2 = 0;
// 如果当前位置比先前的值大，则要考虑取当前值和不取当前值时得到的路径长度。
if(nums[pos] > value) {
path1 = 1 + recursive(pos+1, nums[pos])
}
//不论当前位置的值大小，都需要考察不取当前值的情况
path2 = recursive(pos+1, value)
return Math.max(path1, path2)
}
};
时间复杂度：O(2^n)
空间复杂度：O(n^2)
很遗憾，用此解法在leetcode上运行是无法通过的，时间复杂度太高。
方法二：带记忆能力的递归查找
这个题目的第二个难点在于，如何存储已经查找过的位置。
用一维数组存储明显是不行的，我们存储的目的是避免递归，存储的数值要满足，一定是当前位置往后查找递增子序列时的最优解，如果用一维数组存储：
(错误示例)
var lengthOfLIS = function(nums) {
let memo = []
return recursive(0, -Infinity)
function recursive(pos, value) {
// 边界处理
if(pos >= nums.length) return 0
// add
if(memo[pos]) return memo[pos]
...
return memo[pos] = Math.max(path1, path2)
}
};
以[5, 7, -24,12,13,2,3,12,5,6,35]为例，记忆数组memo的值是[5, 4, 3, 3, 2, 1, 1, 1, 1, 1, 1]。
其值存在1个问题：仅能记忆从位置0开始的递增子序列，当从位置0开始计算一轮之后，memo的每一项都有了值，下一次再次尝试调用递归，就满足了if(memo[pos])return memo[pos]。也就是，记忆数组并没有记住最优解，其值就不可用。
考虑用二维数组，memo[i][j]表示前一次取的数的位置是num[i]，当前这一次取的数的位置是num[j]。再次访问某个位置时，若其前一个位置也相同，则返回memo[i][j]。
/**
* @param {number[]} nums
* @return {number}
*/
var lengthOfLIS = function(nums) {
let memo = []
for(let i = 0; i < nums.length; i++) {
memo[i] = []
}
return recursive(-1, 0, -Infinity)
function recursive(prePos, pos, value) {
// 边界处理
if(pos >= nums.length) return 0
if(memo[prePos+1][pos]) {
return memo[prePos+1][pos]
}
let path1 = 0, path2 = 0;
if(nums[pos] > value) {
path1 = 1 + recursive(pos, pos+1, nums[pos])
}
path2 = recursive(prePos, pos+1, value)
return memo[prePos+1][pos] = Math.max(path1, path2)
}
};
时间复杂度：O(n^2)
空间复杂度：O(n^2)
方法三：动态规划
以dp[]存储包含当前位置的最大递增子序列长度。
举例：[5, 7, -24, 2, 3,12, 5, 6, 35]
(1)确定初始状态: dp[0] = 1, 即长度为1的数组，最长递增子序列长度也为1。（或者初始态也可以设置为，任意位置都为1，其意义是每个位置的最长递增子序列是至少包含其自身的。）
截屏2021-02-03 14.51.40.png
(2)状态分析，这一步是最难的，找到规律之前，不要失去耐心，一个位置一个位置地考察。
考虑dp[1]的值，很明显，若 nums[1] > nums[0]，则dp[1] = dp[0] + 1，否则dp[1] = 1（初始状态，不改变）。
截屏2021-02-03 15.47.39.png
考虑dp[2]的值，是不是nums[2] > nums[1]，也同样可以得出dp[2] = dp[1] + 1，否则，dp[2] = 1呢？这里是可行的，按这个等式填上dp[2]的值。
截屏2021-02-03 15.44.33.png
考虑dp[3]的值，nums[3] > nums[2]，但不能得出dp[3] = dp[2] + 1 = 3，其实你应该发现了，要满足dp[i] = dp[i-1] + 1，一定是严格递增数组才可以。
若nums[3]仅仅和nums[2]比较大小是不够的，它还需要和前面位置的所有元素都做比较，那比较出大小之后如何记录dp[3]呢？dp[0]~dp[2]上的值就派上用场了。以i表示位置3，j从0走到i-1，若满足nums[i] > nums[j]，则dp[i] = dp[j] + 1，否则保持不变。
截屏2021-02-03 16.28.43.png
截屏2021-02-03 16.29.08.png
截屏2021-02-03 16.29.37.png
用此思路尝试填入余下的值，并校验正确性
截屏2021-02-03 16.47.12.png
同时，也要校验dp[1]和dp[2]是否也可以按此状态转移得出。若不行，则考虑特殊处理。
代码实现：
/**
* @param {number[]} nums
* @return {number}
* */
var lengthOfLIS = function(nums) {
let size = nums.length;
if(size <= 1) return size
let dp = []
let path = 0
for(let i = 0; i < size; 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)
}
}
path = Math.max(path, dp[i])
}
return path;
};
时间复杂度：O(n^2)
空间复杂度：O(n)
屏幕快照 2021-03-28 下午3.02.30.png
网友评论