1143.最長(zhǎng)公共子序列?
給定兩個(gè)字符串?text1 和?text2，返回這兩個(gè)字符串的最長(zhǎng)公共子序列的長(zhǎng)度。子序列是由原字符串在不改變字符的相對(duì)順序的情況下刪除某些字符后組成的新字符串。
思路：
dp數(shù)組：長(zhǎng)度為[0, i - 1]的字符串text1與長(zhǎng)度為[0, j - 1]的字符串text2的最長(zhǎng)公共子序列為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]的最長(zhǎng)公共子序列 和 text1[0, i - 1]與text2[0, j - 2]的最長(zhǎng)公共子序列，取最大的。dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
1035.不相交的線???
我們?cè)趦蓷l獨(dú)立的水平線上按給定的順序?qū)懴?A?和?B?中的整數(shù)。現(xiàn)在，我們可以繪制一些連接兩個(gè)數(shù)字?A[i]?和?B[j]?的直線，只要?A[i] == B[j]，且我們繪制的直線不與任何其他連線（非水平線）相交。以這種方法繪制線條，并返回我們可以繪制的最大連線數(shù)。
思路：直線不能相交，這就是說(shuō)明在字符串A中 找到一個(gè)與字符串B相同的子序列，且這個(gè)子序列不能改變相對(duì)順序，只要相對(duì)順序不改變，鏈接相同數(shù)字的直線就不會(huì)相交。那就和前一題“最長(zhǎng)公共子序列”一模一樣了。
53.?最大子序和??動(dòng)態(tài)規(guī)劃?
給定一個(gè)整數(shù)數(shù)組 nums?，找到一個(gè)具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個(gè)元素），返回其最大和。
思路：其實(shí)思路和貪婪算法一樣，直觀的算法。
以下是卡哥資料
1143.最長(zhǎng)公共子序列?
體會(huì)一下本題和?718.?最長(zhǎng)重復(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.最長(zhǎng)公共子序列?是一模一樣的，大家嘗試自己做一做。
視頻講解：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.?最大子序和?
這道題我們用貪心做過(guò)，這次?再用dp來(lái)做一遍?
