代码随想三刷动态规划篇10
300. 最长递增子序列
题目
代码
class Solution {
public int lengthOfLIS(int[] nums) {
if(nums.length==0){
return 0;
}
//dp[i] 以i个为结尾的最长递增子序列长度
int[] dp = new int[nums.length];
dp[0] = 1;
int res = 1;
Arrays.fill(dp, 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[i],dp[j]+1);
}
}
res = Math.max(res, dp[i]);
}
return res;
}
}
674. 最长连续递增序列
题目
代码
class Solution {
public int findLengthOfLCIS(int[] nums) {
if(nums.length==0){
return 0 ;
}
int result = 1;
int temp = 1;
for(int i =1;i<nums.length;i++){
if(nums[i]>nums[i-1]){
temp++;
result = Math.max(result,temp);
}else{
temp = 1;
}
}
return result;
}
}
718. 最长重复子数组
题目
代码
class Solution {
public int findLength(int[] nums1, int[] nums2) {
// 以num1[i]为结尾,以num2[j]为结尾,最长xxx
int[][] dp = new int[nums1.length+1][nums2.length+1];
int res = 0;
//dp[i][j] = dp[i-1][j-1]+1;
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;
}
}
1143. 最长公共子序列
题目
代码
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
char[] arr1 = text1.toCharArray();
char[] arr2 = text2.toCharArray();
int[][] dp = new int[arr1.length+1][arr2.length+1];
for(int i =1;i<=arr1.length;i++){
for(int j =1;j<=arr2.length;j++){
if(arr1[i-1]==arr2[j-1]){
dp[i][j] = dp[i - 1][j - 1] + 1;
}else{
dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
}
}
}
return dp[arr1.length][arr2.length];
}
}
1035. 不相交的线
题目
代码
class Solution {
public int maxUncrossedLines(int[] nums1, int[] nums2) {
//以nums1[i-1]结尾和 nums2[j-1]结尾 最大连线数
int[][] dp = new int[nums1.length+1][nums2.length+1];
//dp[i][j] = dp[i-1][j-1] + 1;
//dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
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;
}else{
dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
}
}
}
return dp[nums1.length][nums2.length];
}
}
原文地址:https://blog.csdn.net/qq_38367575/article/details/140306820
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!