代码随想录训练营 DP序列

最后一题很巧妙，不能单纯的去把DP当作板子题，得思考才能得到最佳方式

718. 最长重复子数组🌸

给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度 。

code

func findLength(A []int, B []int) int {m, n := len(A), len(B)res := 0dp := make([][]int, m+1)for i := 0; i <= m; i++ { dp[i] = make([]int, n+1)}for i := 1; i <= m; i++ {for j := 1; j <= n; j++ {if A[i-1] == B[j-1] {dp[i][j] = dp[i-1][j-1] + 1}if dp[i][j] > res {res = dp[i][j]}}}return res
}

674. 最长连续递增序列🌸

给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。
连续递增的子序列 可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], …, nums[r - 1], nums[r]] 就是连续递增子序列。

code

func findLengthOfLCIS(nums []int) int {dp:=make([]int,len(nums)+1)dp[0]=1res:=1for i:=1;i<len(nums);i++{if nums[i]>nums[i-1]{dp[i]=dp[i-1]+1}else{dp[i] =1}res = max(res,dp[i])}return res
}
func max(a,b int)int{if a>b{return a}return b
}

300.最长递增子序列🌸

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

code

func lengthOfLIS(nums []int) int {dp:=make([]int,len(nums))for i:= range dp{dp[i] =1}res :=dp[0]for i:=1;i<len(nums);i++{for j:=0;j<i;j++{if nums[i] >nums[j]{dp[i] =max(dp[i],dp[j]+1)}}if dp[i] >res{res = dp[i]}}return res
}
func max( a,b int)int{if a >b{return a}return b
}