代码随想录day44 || 1143 最长公共子序列, 1035 不相交的线, 53 最大子序列和, 392 判断子序列

1143 最长公共子序列

func longestCommonSubsequence(text1 string, text2 string) int {
	// 思路和判断最长公共数组一样
	// dp[i][j] 表示以text1[i], text2[j]为结尾的最长公共子序列的长度
	// if text1[i] == text2[j] {dp[i+1][j+1] = dp[i][j] + 1} else {dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])}
	// 初始化多一行一列表示0
	// print

	var maxCount int
	var dp = make([][]int, len(text1) + 1)
	for idx, _ := range dp {
		dp[idx] = make([]int, len(text2) + 1)
	}

	for i:=0; i<len(text1); i++ {
		for j:=0; j<len(text2); j++{
			if text1[i] == text2[j] {
				dp[i+1][j+1] = dp[i][j] + 1
			} else {
				dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])
			}
			if dp[i+1][j+1] > maxCount{
				maxCount = dp[i+1][j+1]
			}
		}
	}
	//fmt.Println(dp)
	return maxCount
}

// 理解递推公式，本身dp[i][j] 已经是之前和之左最大值情况了，所以，不应该考虑使用遍历然后，取最大值来作为递推公式

1035 不相交的线

func maxUncrossedLines(nums1 []int, nums2 []int) int {
	// 难点在于能不能想到本题就是最长公共子序列？
	
	var maxCount int
	var dp = make([][]int, len(nums1) + 1)
	for idx, _ := range dp {
		dp[idx] = make([]int, len(nums2) + 1)
	}

	for i:=0; i<len(nums1); i++ {
		for j:=0; j<len(nums2); j++{
			if nums1[i] == nums2[j] {
				dp[i+1][j+1] = dp[i][j] + 1
			} else {
				dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])
			}
			if dp[i+1][j+1] > maxCount{
				maxCount = dp[i+1][j+1]
			}
		}
	}
	//fmt.Println(dp)
	return maxCount
}

最大子序列和

func maxSubArray(nums []int) int {
	// 贪心的思路，分别存储连续和以及最大和，连续和不断贪心往后累加，如果大于最大和就更新最大和
	// 连续和更新逻辑，如果目前大于0，往后累加，如果小于0，舍弃，直接等于当前元素

	//var sum, maxsum int
	//maxsum = math.MinInt
	//for _, v := range nums {
	//	if sum >= 0 {
	//		sum += v
	//	}else {
	//		sum = v
	//	}
	//
	//	if sum > maxsum {
	//		maxsum = sum
	//	}
	//}
	//return maxsum

	// 动态规划的思路，本题要求最大和，dp[i] 就定义为到nums[i-1]为止的最大子序和
	// 递推公式,
	//		if dp[i-1] > 0  { // 如果前面连续和大于0 对下一个有增加所用，增加
	//			dp[i] = dp[i-1] + nums[i]
	//		}else {
	//			dp[i] = nums[i]
	//		}
	// 初始化dp[0] = nums[0]
	// 遍历数组
	// print
	var dp = make([]int, len(nums))
	dp[0] = nums[0]
	var maxSum = dp[0]

	for i:=1; i<len(nums); i++ {
		if dp[i-1] > 0  { // 如果前面连续和大于0 对下一个有增加所用，增加
			dp[i] = dp[i-1] + nums[i]
		}else {
			dp[i] = nums[i]
		}
		if dp[i] > maxSum{
			maxSum = dp[i]
		}
	}
	fmt.Println(dp)
	return maxSum
}

判断子序列

func isSubsequence(s string, t string) bool {
	// 最简单思路直接hash表计算了，但是我偏要用动规, 思路大概是判断最长公共字串长度是不是等于len(s), 剪枝情况大概是一次遍历没出现
	// dp[i][j] 表示s[i], t[j] 结尾最长字串长度
	// if s[i] == t[j] {dp[i][j] = dp[i-1][j-1] + 1} else {dp[i][j] = max(dp[i-1][j], dp[i][j-1])}
	// 多初始化一行一列
	// print
	if len(s) > len(t) {
		return false
	}
	var maxCount = 0
	var dp = make([][]int, len(s) + 1)
	for idx, _ := range dp {
		dp[idx] = make([]int, len(t) + 1)
	}

	for i:=0; i<len(s); i++ {
		var flag bool
		for j:=0; j<len(t); j++ {
			if s[i] == t[j] {
				flag = true
				dp[i+1][j+1] = dp[i][j] + 1
			}else {
				dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])
			}

			if dp[i+1][j+1] > maxCount {
				maxCount = dp[i+1][j+1]
			}
		}
		if !flag{
			return false
		}
	}
	//fmt.Println(dp)
	if maxCount == len(s){
		return true
	}
	return false
}