第九章 动态规划part13● 300.最长递增子序列
● 674. 最长连续递增序列
● 718. 最长重复子数组 详细布置 300.最长递增子序列 今天开始正式子序列系列，本题是比较简单的，感受感受一下子序列题目的思路。
视频讲解：https://www.bilibili.com/video/BV1ng411J7xP
https://programmercarl.com/0300.%E6%9C%80%E9%95%BF%E4%B8%8A%E5%8D%87%E5%AD%90%E5%BA%8F%E5%88%97.html674. 最长连续递增序列 本题相对于昨天的动态规划：300.最长递增子序列 最大的区别在于“连续”。 先尝试自己做做，感受一下区别
视频讲解：https://www.bilibili.com/video/BV1bD4y1778v
https://programmercarl.com/0674.%E6%9C%80%E9%95%BF%E8%BF%9E%E7%BB%AD%E9%80%92%E5%A2%9E%E5%BA%8F%E5%88%97.html 718. 最长重复子数组 稍有难度，要使用二维dp数组了
视频讲解：https://www.bilibili.com/video/BV178411H7hV
https://programmercarl.com/0718.%E6%9C%80%E9%95%BF%E9%87%8D%E5%A4%8D%E5%AD%90%E6%95%B0%E7%BB%84.html
往日任务
● day 1 任务以及具体安排：https://docs.qq.com/doc/DUG9UR2ZUc3BjRUdY
● day 2 任务以及具体安排：https://docs.qq.com/doc/DUGRwWXNOVEpyaVpG
● day 3 任务以及具体安排：https://docs.qq.com/doc/DUGdqYWNYeGhlaVR6
● day 4 任务以及具体安排：https://docs.qq.com/doc/DUFNjYUxYRHRVWklp
● day 5 周日休息
● day 6 任务以及具体安排：https://docs.qq.com/doc/DUEtFSGdreWRuR2p4
● day 7 任务以及具体安排：https://docs.qq.com/doc/DUElCb1NyTVpXa0Jj
● day 8 任务以及具体安排：https://docs.qq.com/doc/DUGdsY2JFaFhDRVZH
● day 9 任务以及具体安排：https://docs.qq.com/doc/DUHVXSnZNaXpVUHN4
● day 10 任务以及具体安排：https://docs.qq.com/doc/DUElqeHh3cndDbW1Q
●day 11 任务以及具体安排：https://docs.qq.com/doc/DUHh6UE5hUUZOZUd0
●day 12 周日休息
●day 13 任务以及具体安排：https://docs.qq.com/doc/DUHNpa3F4b2dMUWJ3
●day 14 任务以及具体安排：https://docs.qq.com/doc/DUHRtdXZZSWFkeGdE
●day 15 任务以及具体安排：https://docs.qq.com/doc/DUHN0ZVJuRmVYeWNv
●day 16 任务以及具体安排：https://docs.qq.com/doc/DUHBQRm1aSWR4T2NK
●day 17 任务以及具体安排：https://docs.qq.com/doc/DUFpXY3hBZkpabWFY
●day 18 任务以及具体安排：https://docs.qq.com/doc/DUFFiVHl3YVlReVlr
●day 19 周日休息
●day 20 任务以及具体安排：https://docs.qq.com/doc/DUGFRU2V6Z1F4alBH
●day 21 任务以及具体安排：https://docs.qq.com/doc/DUHl2SGNvZmxqZm1X
●day 22 任务以及具体安排：https://docs.qq.com/doc/DUHplVUp5YnN1bnBL
●day 23 任务以及具体安排：https://docs.qq.com/doc/DUFBUQmxpQU1pa29C
●day 24 任务以及具体安排：https://docs.qq.com/doc/DUEhsb0pUUm1WT2NP
●day 25 任务以及具体安排：https://docs.qq.com/doc/DUExTYXVzU1BiU2Zl
●day 26 休息
●day 27 任务以及具体安排：https://docs.qq.com/doc/DUElpbnNUR3hIbXlY
●day 28 任务以及具体安排：https://docs.qq.com/doc/DUG1yVHdlWEdNYlhZ
●day 29 任务以及具体安排：https://docs.qq.com/doc/DUHZYbWhwSHRCRmp3
●day 30 任务以及具体安排：https://docs.qq.com/doc/DUEdTVVhxbnJiY3BR
●day 31 任务以及具体安排：https://docs.qq.com/doc/DUG1PQ1ZZY2xXY1ly
●day 32 任务以及具体安排：https://docs.qq.com/doc/DUGFEdGFWeVhleFF1
●day 33 周日休息
●day 34 任务以及具体安排：https://docs.qq.com/doc/DUEh5WFVlQkp1U0p4
●day 35 任务以及具体安排：https://docs.qq.com/doc/DUFRWc3BGRHFXZ1pO
●day 36 任务以及具体安排：https://docs.qq.com/doc/DUERGbnhhRkFRVENZ
●day 37 任务以及具体安排：https://docs.qq.com/doc/DUFVRd3p5SHFMSExQ
●day 38 任务以及具体安排：https://docs.qq.com/doc/DUGNUdVpoT0VJR01l
●day 39 任务以及具体安排：https://docs.qq.com/doc/DUE55cVJ5WkNoREhS
●day 40 周日休息
●day 41 任务以及具体安排：https://docs.qq.com/doc/DUFhIUXRFYnVGUkFp
●day 42 任务以及具体安排：42 第八章 动态规划
●day 43 任务以及具体安排：43第八章 动态规划
●day 44 任务以及具体安排：44 第八章 动态规划
●day 45 任务以及具体安排：45 第八章 动态规划
●day 46 任务以及具体安排：46 第八章 动态规划
●day 47 周日休息
●day 48 任务以及具体安排：48 第八章 动态规划
●day 49 任务以及具体安排：49 第八章 动态规划
●day 50 任务以及具体安排：50 第八章 动态规划
●day 51 任务以及具体安排：51 第八章 动态规划
day52
最长递增子序列
class Solution {public int lengthOfLIS(int[] nums) {if (nums.length <= 1) return nums.length;int[] dp = new int[nums.length];//以i为结尾的最长递增子序列长度int res = 1;//至少长度为1Arrays.fill(dp, 1);for (int i = 1; i < dp.length; i++) {for (int j = 0; j < i; j++) {if (nums[i] > nums[j]) {dp[i] = Math.max(dp[i], dp[j] + 1);}}res = Math.max(res, dp[i]);}return res;}}
最长连续递增子序列
class Solution {public static int findLengthOfLCIS(int[] nums) {int[] dp = new int[nums.length];for (int i = 0; i < dp.length; i++) {dp[i] = 1;//初始化为1,可以初始化为0吗?不可以,例如312,dp[1] = 0,dp[2] = 1;//为什么非连续子序列可以初始化为0?if (nums[i] > nums[j]) dp[i] = Math.max(dp[i], dp[j] + 1);//也应该赋成1,不然也会出错}int res = 1;for (int i = 0; i < nums.length - 1; i++) {if (nums[i + 1] > nums[i]) {dp[i + 1] = dp[i] + 1;}res = res > dp[i + 1] ? res : dp[i + 1];}return res;}}
最长重复子数组
class Solution {public int findLength(int[] nums1, int[] nums2) {int result = 0;int[][] dp = new int[nums1.length + 1][nums2.length + 1]; //避免初始化的麻烦//什么时候dp需要是length + 1?//不太理解卡哥说的方法二不从零开始会漏掉一种情况什么意思是for (int i = 1; i < nums1.length + 1; i++) {for (int j = 1; j < nums2.length + 1; j++) {if (nums1[i - 1] == nums2[j - 1]) {dp[i][j] = dp[i - 1][j - 1] + 1;result = Math.max(result, dp[i][j]);}}} return result;}}
感谢大佬分享:
代码随想录-算法训练营day52【动态规划13：最长递增子序列、最长连续递增序列、最长重复子数组】-CSDN博客