代码随想录算法训练营第四十三天 | leetcode：最长递增子序列,最长连续递增序列 ,最长重复子数组
0 / 0 / 创建于 11个月前
_zzh 的个人博客
300. 最长递增子序列
解题方法
- dp数组的含义：dp[i]：表示i之前包括i的以nums[i]结尾的最长递增子序列的长度
- 状态转移方程：if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1)
位置i的最长升序子序列等于j从0到i-1各个位置的最长升序子序列 + 1 的最大值。
注意这里不是要dp[i] 与 dp[j] + 1进行比较，而是我们要取dp[j] + 1的最大值。- 初始化dp数组：每一个i，对应的dp[i]（即最长递增子序列）起始大小至少都是1.所以dp数组都需要初始化为1.
- 遍历顺序：i依赖于j， 而j<i 所以遍历顺序是从前往后。
code
class Solution {
/**
* @param Integer[] $nums
* @return Integer
*/
function lengthOfLIS($nums) {
$len = count($nums);
if($len == 1) return $len;
$dp = array_fill(0,$len,1);
$result = 0;
for($i = 1; $i < $len; $i++){
for($j = 0; $j < $i; $j++){
if($nums[$j] < $nums[$i]){
$dp[$i] = max($dp[$i], $dp[$j] + 1);
}
}
//收集dp数值里面最大的值
if($dp[$i] > $result) $result = $dp[$i];
}
return $result;
}
}复杂度
时间复杂度
O(n^2)
空间复杂度
O(n)
674. 最长连续递增序列
解题方法
- dp数组的含义：dp[i]：以下标i为结尾的连续递增的子序列长度为dp[i]
- 确定递推公式：dp[i] = dp[i - 1] + 1;
如果 nums[i] > nums[i - 1]，那么以 i 为结尾的连续递增的子序列长度 一定等于 以i - 1为结尾的连续递增的子序列长度 + 1- 初始化dp数组：以下标i为结尾的连续递增的子序列长度最少也应该是1，即就是nums[i]这一个元素。
所以dp[i]应该初始1;- 遍历顺序：dp[i + 1]依赖dp[i]，所以一定是从前向后遍历。
code
class Solution {
/**
* @param Integer[] $nums
* @return Integer
*/
function findLengthOfLCIS($nums) {
$len = count($nums);
if($len == 1) return $len;
$dp = array_fill(0,$len,1);
$res = 1;
for($i = 1; $i < $len; $i++){
if($nums[$i] > $nums[$i-1]){
$dp[$i] = $dp[$i-1] + 1;
}
//收集dp数值里面最大的值
if($dp[$i] > $res) $res = $dp[$i];
}
return $res;
}
}复杂度
时间复杂度
O(n)
空间复杂度
O(n)
718. 最长重复子数组
解题方法
- dp数组的含义：dp[i][j] ：以下标i - 1为结尾的A，和以下标j - 1为结尾的B，最长重复子数组长度为dp[i][j]。
（特别注意： “以下标i - 1为结尾的A” 标明一定是 以A[i-1]为结尾的字符串 ）- 确定递推公式：dp[i][j]的状态只能由dp[i - 1][j - 1]推导出来。
即当A[i - 1] 和B[j - 1]相等的时候，dp[i][j] = dp[i - 1][j - 1] + 1;
根据递推公式可以看出，遍历i 和 j 要从1开始！- 初始化dp数组：dp[i][0] 和dp[0][j]其实都是没有意义的！所以都初始化为0。其他值，因为会被覆盖，所以统一初始化为0
- 遍历顺序：外层for循环遍历nums1，内层for循环遍历nums2。
code
class Solution {
/**
* @param Integer[] $nums1
* @param Integer[] $nums2
* @return Integer
*/
function findLength($nums1, $nums2) {
$dp = [];
$len1 = count($nums1);
$len2 = count($nums2);
//因为递推公式含义是i-1结尾，j-1结尾，所以循环要<=len不然遍历不到最后一个元素
for($i = 0; $i <= $len1; $i++){
for($j = 0; $j <= $len2; $j++){
$dp[$i][$j] = 0;
}
}
$res = 0;
for($i = 1; $i <= $len1; $i++){
for($j = 1; $j <= $len2; $j++){
if($nums1[$i-1] == $nums2[$j-1]){
$dp[$i][$j] = $dp[$i-1][$j-1] + 1;
}
if($dp[$i][$j] > $res) $res = $dp[$i][$j];
}
}
//print_r($dp);
return $res;
}
}复杂度
时间复杂度
O(n × m)，n 为nums1长度，m为nums2长度
空间复杂度
O(n × m)
本作品采用《CC 协议》，转载必须注明作者和本文链接
关于 LearnKu
粤公网安备 44030502004330号