题目：1143. 最长公共子序列
思路：
主要就是两大情况： text1[i - 1] 与 text2[j - 1]相同，text1[i - 1] 与 text2[j - 1]不相同
-
如果
text1[i - 1]与text2[j - 1]相同，那么找到了一个公共元素，所以dp[i][j] = dp[i - 1][j - 1] + 1; -
如果
text1[i - 1] 与 text2[j - 1]不相同，那就看看text1[0, i - 2]与text2[0, j - 1]的最长公共子序列 和text1[0, i - 1]与text2[0, j - 2]的最长公共子序列，取最大的。
即：dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
代码：
func longestCommonSubsequence(text1 string, text2 string) int {
lens1 := len(text1)
lens2 := len(text2)
dp := make([][]int, lens1 + 1)
for i := 0; i <= lens1; i++ {
dp[i] = make([]int, lens2 + 1)
}
res := dp[0][0]
for i := 1; i <=lens1; i++ {
for j := 1; j <= lens2; j++ {
if text1[i-1] == text2[j-1] {
dp[i][j] = dp[i-1][j-1] + 1
}else {
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
}
if dp[i][j] > res {
res = dp[i][j]
}
}
}
return res
}
func max(a,b int) int {
if a > b {
return a
}
return b
}
参考：
题目：1035. 不相交的线
思路：
仔细想想这其实就是最长公共子序列，只是把字符的匹配变成了数字的匹配而已。
代码：
func maxUncrossedLines(nums1 []int, nums2 []int) int {
lens1 := len(nums1)
lens2 := len(nums2)
dp := make([][]int, lens1 + 1)
for i := 0; i <= lens1; i++ {
dp[i] = make([]int, lens2 + 1)
}
res := dp[0][0]
for i := 1; i <=lens1; i++ {
for j := 1; j <= lens2; j++ {
if nums1[i-1] == nums2[j-1] {
dp[i][j] = dp[i-1][j-1] + 1
}else {
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
}
if dp[i][j] > res {
res = dp[i][j]
}
}
}
return res
}
func max(a,b int) int {
if a > b {
return a
}
return b
}
参考：
题目：53. 最大子数组和
思路：
也是贪心的DP，贪心的DP一般状态转移只需要考虑前一个或者后一个元素的情况。
代码：
func maxSubArray(nums []int) int {
lens := len(nums)
dp := make([]int, lens + 1)
res := -math.MaxInt
for i := 1; i <= lens; i++ {
dp[i] = max(dp[i-1] + nums[i-1], nums[i-1])
if dp[i] > res {
res = dp[i]
}
}
return res
}
func max(a,b int) int {
if a > b {
return a
}
return b
}