1143.最長公共子序列?
給定兩個(gè)字符串?text1 和?text2,返回這兩個(gè)字符串的最長公共子序列的長度。子序列是由原字符串在不改變字符的相對順序的情況下刪除某些字符后組成的新字符串。
思路:
dp數(shù)組:長度為[0, i - 1]的字符串text1與長度為[0, j - 1]的字符串text2的最長公共子序列為dp[i][j],初始化為0.
遞推公式:如果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]);
1035.不相交的線???
我們在兩條獨(dú)立的水平線上按給定的順序?qū)懴?A?和?B?中的整數(shù)》缯郑現(xiàn)在糠排,我們可以繪制一些連接兩個(gè)數(shù)字?A[i]?和?B[j]?的直線,只要?A[i] == B[j]超升,且我們繪制的直線不與任何其他連線(非水平線)相交入宦。以這種方法繪制線條哺徊,并返回我們可以繪制的最大連線數(shù)。
思路:直線不能相交乾闰,這就是說明在字符串A中 找到一個(gè)與字符串B相同的子序列落追,且這個(gè)子序列不能改變相對順序,只要相對順序不改變涯肩,鏈接相同數(shù)字的直線就不會(huì)相交轿钠。那就和前一題“最長公共子序列”一模一樣了。
53.?最大子序和??動(dòng)態(tài)規(guī)劃?
給定一個(gè)整數(shù)數(shù)組 nums?病苗,找到一個(gè)具有最大和的連續(xù)子數(shù)組(子數(shù)組最少包含一個(gè)元素)疗垛,返回其最大和。
思路:其實(shí)思路和貪婪算法一樣硫朦,直觀的算法贷腕。
以下是卡哥資料
1143.最長公共子序列?
體會(huì)一下本題和?718.?最長重復(fù)子數(shù)組?的區(qū)別??
視頻講解:https://www.bilibili.com/video/BV1ye4y1L7CQ
https://programmercarl.com/1143.%E6%9C%80%E9%95%BF%E5%85%AC%E5%85%B1%E5%AD%90%E5%BA%8F%E5%88%97.html
?1035.不相交的線?
其實(shí)本題和?1143.最長公共子序列?是一模一樣的,大家嘗試自己做一做咬展。
視頻講解:https://www.bilibili.com/video/BV1h84y1x7MP
https://programmercarl.com/1035.%E4%B8%8D%E7%9B%B8%E4%BA%A4%E7%9A%84%E7%BA%BF.html
?53.?最大子序和?
這道題我們用貪心做過泽裳,這次?再用dp來做一遍?