本文主要是介绍算法训练营day45(补)，动态规划13，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
package main
func max(a, b int) int {
if a > b {
return a
}
return b
}
//1143. 最长公共子序列
func longestCommonSubsequence(text1 string, text2 string) int {
n := len(text1)
h := len(text2)
dp := make([][]int, n+1)
for i := 0; i <= n; i++ {
dp[i] = make([]int, h+1)
}
num := 0
for i := 1; i <= n; i++ {
for j := 1; j <= h; j++ {
/*本题与求最长重复子序列相似，不同之处在于不要求是连续的了，但要有相对顺序， 即："ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。 因此text1[i-1]和 text2[j-1] 相同一样，直接+1，不相同则在dp[i][j-1]与dp[i-1][j]之间取最大值*/
if text1[i-1] == text2[j-1] {
dp[i][j] = dp[i-1][j-1] + 1
} else {
dp[i][j] = max(dp[i][j-1], dp[i-1][j])
}
if dp[i][j] > num {
num = dp[i][j]
}
}
}
return num
}
//1035. 不相交的线
//本质上还是求最长公共子序列
func maxUncrossedLines(nums1 []int, nums2 []int) int {
n := len(nums1)
h := len(nums2)
dp := make([][]int, n+1)
for i := 0; i <= n; i++ {
dp[i] = make([]int, h+1)
}
num := 0
for i := 1; i <= n; i++ {
for j := 1; j <= h; j++ {
if nums1[i-1] == nums2[j-1] {
dp[i][j] = dp[i-1][j-1] + 1
} else {
dp[i][j] = max(dp[i][j-1], dp[i-1][j])
}
if dp[i][j] > num {
num = dp[i][j]
}
}
}
return num
}
//53. 最大子数组和
func maxSubArray(nums []int) int {
dp := make([]int, len(nums))
dp[0] = nums[0]
//最大值初始值为数组第一个数，不能给0
sum := nums[0]
for i := 1; i < len(nums); i++ {
// 求最大子数组和就是让nums数组当前值和dp数组上一个值相加，在与nums数组当前比较，取最大值
dp[i] = max(dp[i-1]+nums[i], nums[i])
if dp[i] > sum {
sum = dp[i]
}
}
return sum
}
这篇关于算法训练营day45(补)，动态规划13的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
