门户网站盈利模式,西安网站托管商家,网络免费推广平台,做网站大概要多久300.最长递增子序列 看完题后的思路
dp[i] [0,i]子数组中,以nums[i]结尾的子序列的长度 dp[i]dp[j]1 j从i-1向0遍历,在所有nums[j]nums[i]中dp[j]最大 初始化 dp[0]1
代码
class Solution {public int lengthOfLIS(int[] nums) {if (nums.length0){return 0;}int[] dpne…300.最长递增子序列 看完题后的思路
dp[i] [0,i]子数组中,以nums[i]结尾的子序列的长度 dp[i]dp[j]1 j从i-1向0遍历,在所有nums[j]nums[i]中dp[j]最大 初始化 dp[0]1
代码
class Solution {public int lengthOfLIS(int[] nums) {if (nums.length0){return 0;}int[] dpnew int[nums.length];dp[0]1;for (int i 1; i nums.length ; i) {int j i-1;int max-1;for (; j 0 ; j--) {if (nums[j]nums[i]dp[j]max){dp[i]dp[j]1;maxdp[j];}} if (max-1){dp[i]1;}}int max0;for (int i : dp) {maxMath.max(i,max);}return max;}
}看完题解的改进
dp【i】maxdp【i】dp【j】1 nums【j】nums【i】
674. 最长连续递增序列
看完题后的思路
dp[i]dp[i-1]1 nums[i]nums[i-1] dp[i]1 else
代码 public int findLengthOfLCIS(int[] nums) {int[] dp new int[nums.length];dp[0]1;int max1;for (int i 1; i nums.length ; i) {if (nums[i]nums[i-1]){dp[i]dp[i-1]1;}else {dp[i]1;}maxMath.max(dp[i],max);}return max;}718. 最长重复子数组 看完题后的思路
dp[i][j]: 包含以A[i]结尾与以B[j]结尾的公共序列的长度 dp[i][j]dp[i-1][j-1]1 A[i]B[j] else 0 初始化 dp[0][j] 0/1 dp[i][0]0/1
代码 public int findLength(int[] nums1, int[] nums2) {int mnums1.length,nnums2.length;int max0;int[][] dpnew int[m][n];for (int i 0; i n ; i) {if (nums1[0]nums2[i]){dp[0][i]1;}else {dp[0][i]0;}maxMath.max(dp[0][i],max);}for (int i 0; i m ; i) {if (nums2[0]nums1[i]){dp[i][0]1;}else {dp[i][0]0;}maxMath.max(dp[i][0],max);}// 核心for (int i 1; i m ; i) {for (int j 1; j n ; j) {if (nums1[i]nums2[j]){dp[i][j]dp[i-1][j-1]1;}else {dp[i][j]0;}maxMath.max(dp[i][j],max);}}return max;}
