300.最长递增子序列
题目
参考文章
思路：dp[i]表示i之前包括i的以nums[i]结尾的最长递增子序列的长度
因为没有连续，所以每一个元素都要比较，从而得到结果
两个递增子序列一定分别以nums[j]为结尾 和 nums[i]为结尾， 要不然这个比较就没有意义了
位置i的最长升序子序列等于j从0到i-1各个位置的最长升序子序列 + 1 的最大值。
所以：if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);
注意这里不是要dp[i] 与 dp[j] + 1进行比较，而是我们要取dp[i]和dp[j] + 1的最大值。
初始长度都为1
而且不需要遍历第一个元素（即i=0的情况，因为只能是1）
代码：
class Solution {public int lengthOfLIS(int[] nums) {if(nums.length<=1){return nums.length;}int[] dp=new int[nums.length];int res=1;Arrays.fill(dp,1);//初始化dp数组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[i],dp[j]+1);//得到的长度，就是找递增子序列中最长的长度}res=Math.max(res,dp[i]);//找res即可，因为上一层循环每次都会遍历一次dp[i],所以找一个中间值来做最后的运算。}}return res;}
}674. 最长连续递增序列
题目
参考文章
思路：与300.最长递增子序列有些不同
dp[i]：以下标i为结尾的连续递增的子序列长度为dp[i]。
可以不用遍历之前前面的所有元素，只要比较前一个元素即可
如果 nums[i] > nums[i - 1]，那么以 i 为结尾的连续递增的子序列长度 一定等于 以i - 1为结尾的连续递增的子序列长度 + 1 。
即：dp[i] = dp[i - 1] + 1;
所以就只要比较nums[i]与nums[i - 1]，而不用去比较nums[j]与nums[i] （j是在0到i之间遍历）。
代码：
class Solution {public int findLengthOfLCIS(int[] nums) {int[] dp=new int[nums.length];for(int i=0;i<nums.length;i++){dp[i]=1;}int res=1;for(int i=1;i<nums.length;i++){if(nums[i]>nums[i-1]){dp[i]=dp[i-1]+1;}res=Math.max(res,dp[i]);}return res;}
}718. 最长重复子数组
题目
参考文章
思路：其实是有难度的，因为难以想到用动态规划的方式去解决
dp[i][j] ：以下标i - 1为结尾的A，和以下标j - 1为结尾的B，最长重复子数组长度为dp[i][j]。 （特别注意： “以下标i - 1为结尾的A” 标明一定是 以A[i-1]为结尾的字符串 ）
根据dp[i][j]的定义，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[i][j]的定义，dp[i][0] 和dp[0][j]其实都是没有意义的！
但dp[i][0] 和dp[0][j]要初始值，因为 为了方便递归公式dp[i][j] = dp[i - 1][j - 1] + 1;
所以dp[i][0] 和dp[0][j]初始化为0。
dp[i][j]=dp[i-1][j-1]+1;//记录当前重复数组长度，这步不能写到max函数中，否则dp[i][j]存储不到值
代码：
class Solution {public int findLength(int[] nums1, int[] nums2) {int res=0;int[][] dp=new int[nums1.length+1][nums2.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;//记录当前重复数组长度，这步不能写到max函数中，否则dp[i][j]存储不到值res=Math.max(res,dp[i][j]);}}}return res;}
}
