第四十六天 | 1143.最長公共子序列 1035.不相交的線 53. 最大子序和 動(dòng)態(tài)規(guī)劃

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來做一遍?

視頻講解:https://www.bilibili.com/video/BV19V4y1F7b5

https://programmercarl.com/0053.%E6%9C%80%E5%A4%A7%E5%AD%90%E5%BA%8F%E5%92%8C%EF%BC%88%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%EF%BC%89.html

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個(gè)濱河市挚赊,隨后出現(xiàn)的幾起案子诡壁,更是在濱河造成了極大的恐慌济瓢,老刑警劉巖荠割,帶你破解...
    沈念sama閱讀 222,946評論 6 518
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場離奇詭異旺矾,居然都是意外死亡蔑鹦,警方通過查閱死者的電腦和手機(jī),發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,336評論 3 399
  • 文/潘曉璐 我一進(jìn)店門箕宙,熙熙樓的掌柜王于貴愁眉苦臉地迎上來嚎朽,“玉大人,你說我怎么就攤上這事柬帕∮慈蹋” “怎么了?”我有些...
    開封第一講書人閱讀 169,716評論 0 364
  • 文/不壞的土叔 我叫張陵陷寝,是天一觀的道長锅很。 經(jīng)常有香客問我,道長凤跑,這世上最難降的妖魔是什么爆安? 我笑而不...
    開封第一講書人閱讀 60,222評論 1 300
  • 正文 為了忘掉前任,我火速辦了婚禮仔引,結(jié)果婚禮上扔仓,老公的妹妹穿的比我還像新娘褐奥。我一直安慰自己,他們只是感情好翘簇,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,223評論 6 398
  • 文/花漫 我一把揭開白布撬码。 她就那樣靜靜地躺著,像睡著了一般版保。 火紅的嫁衣襯著肌膚如雪耍群。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 52,807評論 1 314
  • 那天找筝,我揣著相機(jī)與錄音即寒,去河邊找鬼。 笑死瑞眼,一個(gè)胖子當(dāng)著我的面吹牛恋捆,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播急鳄,決...
    沈念sama閱讀 41,235評論 3 424
  • 文/蒼蘭香墨 我猛地睜開眼谤民,長吁一口氣:“原來是場噩夢啊……” “哼!你這毒婦竟也來了疾宏?” 一聲冷哼從身側(cè)響起张足,我...
    開封第一講書人閱讀 40,189評論 0 277
  • 序言:老撾萬榮一對情侶失蹤,失蹤者是張志新(化名)和其女友劉穎坎藐,沒想到半個(gè)月后为牍,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 46,712評論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡岩馍,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,775評論 3 343
  • 正文 我和宋清朗相戀三年碉咆,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片蛀恩。...
    茶點(diǎn)故事閱讀 40,926評論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡疫铜,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出双谆,到底是詐尸還是另有隱情壳咕,我是刑警寧澤,帶...
    沈念sama閱讀 36,580評論 5 351
  • 正文 年R本政府宣布顽馋,位于F島的核電站谓厘,受9級特大地震影響,放射性物質(zhì)發(fā)生泄漏趣避。R本人自食惡果不足惜庞呕,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,259評論 3 336
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧住练,春花似錦地啰、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,750評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至盏混,卻和暖如春蔚鸥,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背许赃。 一陣腳步聲響...
    開封第一講書人閱讀 33,867評論 1 274
  • 我被黑心中介騙來泰國打工止喷, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留,地道東北人混聊。 一個(gè)月前我還...
    沈念sama閱讀 49,368評論 3 379
  • 正文 我出身青樓弹谁,卻偏偏與公主長得像,于是被迫代替她去往敵國和親句喜。 傳聞我的和親對象是個(gè)殘疾皇子预愤,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,930評論 2 361

推薦閱讀更多精彩內(nèi)容