摘要 通過取模運(yùn)算來模擬在數(shù)組中循環(huán)搜索元素,這比在數(shù)組后拼接一個(gè)相同數(shù)組更方便,空間復(fù)雜度更低。 “接雨水”和“柱狀圖中的最大矩形”,都可以看...
摘要 單調(diào)棧方法的時(shí)間復(fù)雜度是O(n),只需要一層循環(huán)遍歷一次輸入數(shù)組,代碼更簡(jiǎn)潔,邏輯更巧妙。 棧內(nèi)元素從棧頂?shù)綏5走f增(或非遞減),找的是任...
摘要 今天的兩道題目是區(qū)間 dp 的入門題目,以每一個(gè)區(qū)間作為一個(gè)狀態(tài)來定義 dp 數(shù)組和遞推公式。 子串(子字符串)要求元素在原序列(原字符串...
摘要 編輯距離問題中,插入一個(gè)字符和刪除一個(gè)字符,對(duì)于使得兩個(gè)字符串相等的作用是一樣的,都是使得兩個(gè)字符串更加接近,所以可以統(tǒng)一只使用“插入”或...
摘要 套用“最長(zhǎng)公共子序列”的思路,LeetCode392 判斷子序列可以轉(zhuǎn)化為:求s和t的最長(zhǎng)公共子序列的長(zhǎng)度,并判斷這個(gè)最長(zhǎng)公共子序列的長(zhǎng)度...
摘要 如果不要求子序列中的元素在原序列中連續(xù),相比于要求“連續(xù)”,dp數(shù)組的定義和遞推公式是不一樣的。 如果要求“連續(xù)”,那dp數(shù)組定義為以具體...
摘要 如果答案在dp數(shù)組中的位置不是固定的,可以在dp數(shù)組的更新過程中記錄可能的答案,簡(jiǎn)化代碼,例如今天的三道題,都可以在每次更新dp數(shù)組后來記...
摘要 有些動(dòng)態(tài)規(guī)劃的題目的難點(diǎn)在于如何劃分狀態(tài)和這些狀態(tài)之間如何進(jìn)行轉(zhuǎn)移,列出可能的狀態(tài)以及轉(zhuǎn)移到這些狀態(tài)的可能,是定義dp數(shù)組及數(shù)組下標(biāo)、推導(dǎo)...
摘要 只買賣一次股票,和不限制次數(shù)地買賣股票,只是在遞推公式上有差別。而且,這兩種情況都不需要記錄完成買賣的次數(shù)。 指定了至多買k次股票,這就暗...