力扣300.最长递增子序列
题目链接：https://leetcode.cn/problems/longest-increasing-subsequence/
思路
dp数组的含义
dp[i]表示，以nums[i]结尾的最长递增子序列长度
递推公式
假设j在i的前面，如果nums[j]<nums[i]，那么dp[i]至少是dp[j]+1
让j遍历[0,i)的所有元素，位置i的最长递增子序列等于j从0到i-1各个位置的最长递增子序列 + 1 的最大值，即dp[i] = Math.max(dp[j] + 1,dp[i])。
初始化
dp[i]最起码长度为1（自身）
遍历顺序
i必须从前向后遍历，因为要利用在它之前的j的值。
j不论从前向后还是从后向前遍历都行，只需要遍历完[0,i)的元素即可。
打印数组
这里要注意不是dp[nums.length-1]，因为最长子序列不一定是在最后一个元素那里取到。所以要遍历整个nums[i]，找到最大值。
完整代码
class Solution {public int lengthOfLIS(int[] nums) {int[] dp = new int[nums.length];Arrays.fill(dp,1);dp[0] = 1;int result = 1;for (int i = 1; i < nums.length; i++) {for (int j = 0; j < i; j++) {if(nums[i] > nums[j]){dp[i] = Math.max(dp[j] + 1,dp[i]);}}result = Math.max(result,dp[i]);}return result;}
}
力扣674.最长连续递增序列
题目链接：https://leetcode.cn/problems/longest-continuous-increasing-subsequence/
##思路
本题和最长递增子序列不同的点就是：要求连续
递推公式
只需要判断nums[i-1]和nums[i]是不是递增的关系，是递增关系，dp[i] = dp[i-1] + 1。不是递增关系，就保持初始值，即为1。
完整代码
class Solution {public int findLengthOfLCIS(int[] nums) {int[] dp = new int[nums.length];Arrays.fill(dp,1);int result = 1;for (int i = 1; i < nums.length; i++) {if(nums[i] > nums[i-1]){dp[i] = dp[i-1] + 1;}result = Math.max(result,dp[i]);}return result;}
}
力扣718.最长重复子数组
题目链接：https://leetcode.cn/problems/maximum-length-of-repeated-subarray/
思路
dp数组含义
dp[i][j]表示：以nums1[i-1]为结尾，nums2[j-1]为结尾的最长重复子数组
递推公式
匹配到nums1[i-1]==nums2[j-1]时，有dp[i][j] = dp[i-1][j-1] + 1。
这里为什么匹配到i-1和j-1可以得出dp[i][j]的公式呢？
因为在dp数组的定义中，dp[i][j]表示的就是以nums1[i-1]为结尾，nums2[j-1]为结尾的最长重复子数组。
那么为什么是dp[i][j] = dp[i-1][j-1] + 1呢？
因为匹配时，两个数组必须同时回退一格，不能nums1退一格，nums2不退。
初始化
由于我们对dp数组的定义，所以导致dp[0][j]和dp[i][0]是没有意义的，因为dp[i][j]是需要1个1个累加的，所以为了方便，我们将dp数组全部初始化为0.
遍历顺序
两个数组都是从前向后遍历，需要注意的是：i <= nums1.length，这里等号是能取到的，因为我们对dp数组的定义是i-1和j-1。那么同时，dp数组初始化的大小应该涵盖到nums1.length+1
打印数组
这和之前两题类似，不一定会在数组最后一个元素取到最大值，需要遍历整个数组，得到最大值。
完整代码
class Solution {public int findLength(int[] nums1, int[] nums2) {int[][] dp = new int[nums1.length+1][nums2.length+1];int res = 0;for (int i = 1; i <= nums1.length; i++) {for (int j = 1; j <= nums2.length; j++) {if(nums1[i-1] == nums2[j-1]){dp[i][j] = dp[i-1][j-1] + 1;}res = Math.max(res,dp[i][j]);}}return res;}
}
