2022-02-19 動態(tài)規(guī)劃專題

動態(tài)規(guī)劃問題基本解題步驟

  1. 設計狀態(tài)
  2. 寫出狀態(tài)轉移方程
  3. 設置初始狀態(tài)
  4. 處理非法狀態(tài)
  5. 執(zhí)行狀態(tài)轉移
  6. 后處理
  7. 返回最終結果

顯式轉移方程

  • 斐波那契數(shù)列
  • 階乘

隱式轉移方程

  • 爬樓梯
  • 爬樓梯最小花費

注意:對于隱式狀態(tài)轉移方程允跑,可以先從初始的幾個狀態(tài)列舉出來萤皂,看能不能看出規(guī)律

相關題目練習

劍指 Offer 10- I. 斐波那契數(shù)列

一個函數(shù),輸入 n 斜筐,求斐波那契(Fibonacci)數(shù)列的第 n 項(即 F(N))冰啃。斐波那契數(shù)列的定義如下:

F(0) = 0,   F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

斐波那契數(shù)列由 0 和 1 開始邓夕,之后的斐波那契數(shù)就是由之前的兩數(shù)相加而得出肋层。

答案需要取模 1e9+7(1000000007),如計算初始結果為:1000000008翎迁,請返回 1栋猖。

示例 1:

輸入:n = 2
輸出:1

示例 2:

輸入:n = 5
輸出:5

提示:

0 <= n <= 100

題解:

class Solution:
    def fib(self, n: int) -> int:
        n = n % 1000000007
        a = 0
        if n == 0:
            return a
        b = 1    
        if n == 1:
            return b
        
        sum = 0
        for i in range(2, n+1):
            sum = a + b
            a = b
            b =sum
        return sum % 1000000007

70. 爬樓梯

新解法:爬樓梯到當前臺階只能從前一階臺階或前兩階臺階上來:F(n) = F(n - 1) + F(n - 2)

class Solution:
    def climbStairs(self, n: int) -> int:
        init0 = 1
        init1 = 1
        if n <= 1:
            return 1
        for i in range(n - 1):
            ans = init1 + init0
            init0 = init1
            init1 = ans
        return ans

746. 使用最小花費爬樓梯

題解:

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        dp1 = 0
        dp2 = 0
        for i in range(2, len(cost)+1):
            dp = min(dp1 + cost[i-1], dp2 + cost[i-2])
            dp2 = dp1
            dp1 = dp

        return dp1

53. 最大子數(shù)組和

給你一個整數(shù)數(shù)組 nums ,請你找出一個具有最大和的連續(xù)子數(shù)組(子數(shù)組最少包含一個元素)汪榔,返回其最大和蒲拉。

子數(shù)組 是數(shù)組中的一個連續(xù)部分。

示例 1:

輸入:nums = [-2,1,-3,4,-1,2,1,-5,4]
輸出:6
解釋:連續(xù)子數(shù)組 [4,-1,2,1] 的和最大痴腌,為 6 雌团。

示例 2:

輸入:nums = [1]
輸出:1

示例 3:

輸入:nums = [5,4,-1,7,8]
輸出:23

提示:

1 <= nums.length <= 105
-104 <= nums[i] <= 104

分析:

  • 狀態(tài):dp[i] : 以第i個數(shù)結尾的子數(shù)組
  • 狀態(tài)轉移:
    • 第i-1個數(shù)結尾的子數(shù)組加上第i個數(shù)
    • 第i個數(shù)單獨作為子數(shù)組
    • dp[i] = max{dp[i - 1] + num[i], num[i]}
  • 初始狀態(tài)dp[0] = num[0]
  • 最后執(zhí)行狀態(tài),再所有狀態(tài)中取dp最大的狀態(tài)作為結果返回

題解:

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        l = len(nums)
        dp = [0] * l  
        dp[0] = nums[0]
        for i in range(1, l):
            dp[i] = max(dp[i-1] + nums[i], nums[i])
        return max(dp)

優(yōu)化空間:在上述的狀態(tài)轉移中士聪,我們需要一個和原始數(shù)組一樣大的數(shù)組存儲狀態(tài)锦援,但最終我們只需要這些狀態(tài)中的最大值,既然只需要最大值剥悟,那我我們只需要一個空間存最大值灵寺,一個空間取遍歷就好了

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        ans = nums[0]
        sum = nums[0]
        for i in range(1, len(nums)):
            sum = max(sum + nums[i], nums[i])
            if sum > ans:
                ans = sum

        return ans

198. 打家劫舍

你是一個專業(yè)的小偷,計劃偷竊沿街的房屋区岗。每間房內都藏有一定的現(xiàn)金略板,影響你偷竊的唯一制約因素就是相鄰的房屋裝有相互連通的防盜系統(tǒng),如果兩間相鄰的房屋在同一晚上被小偷闖入慈缔,系統(tǒng)會自動報警叮称。

給定一個代表每個房屋存放金額的非負整數(shù)數(shù)組,計算你 不觸動警報裝置的情況下 藐鹤,一夜之內能夠偷竊到的最高金額瓤檐。

示例 1:

輸入:[1,2,3,1]
輸出:4
解釋:偷竊 1 號房屋 (金額 = 1) ,然后偷竊 3 號房屋 (金額 = 3)娱节。
     偷竊到的最高金額 = 1 + 3 = 4 挠蛉。

示例 2:

輸入:[2,7,9,3,1]
輸出:12
解釋:偷竊 1 號房屋 (金額 = 2), 偷竊 3 號房屋 (金額 = 9),接著偷竊 5 號房屋 (金額 = 1)括堤。
     偷竊到的最高金額 = 2 + 9 + 1 = 12 碌秸。

提示:

1 <= nums.length <= 100
0 <= nums[i] <= 400

分析:

  • 確定狀態(tài):dp[i]:判斷偷第i家的狀態(tài)
  • 狀態(tài)轉移:
    • 對于dp[i]這個狀態(tài)绍移,要么偷了第i家悄窃,收益是nums[i] + dp[i-2]
    • 要么沒有偷第i家,收益是偷上一家的dp[i-1]
    • dp[i] = max(nums[i] + dp[i-2], dp[i-1])
  • 初始狀態(tài):
    • 只有一家:dp[0] = nums[0]蹂窖,即這家收益
    • 只有兩家:dp[1] = max(nums[0], nums[1])轧抗,即偷收益多的那家
  • 執(zhí)行狀態(tài),最后一次偷的即最高金額

題解:

class Solution:
    def rob(self, nums: List[int]) -> int:
        l = len(nums)
        if l <= 2:
            return max(nums)

        dp = [0] * l

        dp[0] = nums[0]
        dp[1] = max(nums[0], nums[1])

        for i in range(2, l):
            dp[i] = max(dp[i-1], dp[i-2] + nums[i])

        return dp[-1]

空間優(yōu)化:與上一題類似瞬测,對于求最大部分横媚。如果用的是數(shù)組可以用兩個變量優(yōu)化空間

class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 0: return 0
        dp = [0]*n

        dp2 = 0
        dp1 = 0

        for i in range(0, n):
            dp = max(dp2 + nums[i], dp1)
            dp2 = dp1
            dp1 = dp;
        return dp1

總結:對于出現(xiàn)求最大值需要對此敏感纠炮,如果最大值針對一個數(shù)組狀態(tài),便可以考慮優(yōu)化為兩個變量代替灯蝴,讓空間復雜度由O(n)->O(1)

740. 刪除并獲得點數(shù)

給你一個整數(shù)數(shù)組 nums 恢口,你可以對它進行一些操作。

每次操作中穷躁,選擇任意一個 nums[i] 耕肩,刪除它并獲得 nums[i] 的點數(shù)。之后问潭,你必須刪除 所有 等于 nums[i] - 1 和 nums[i] + 1 的元素猿诸。

開始你擁有 0 個點數(shù)。返回你能通過這些操作獲得的最大點數(shù)狡忙。

示例 1:

輸入:nums = [3,4,2]
輸出:6
解釋:
刪除 4 獲得 4 個點數(shù)梳虽,因此 3 也被刪除。
之后灾茁,刪除 2 獲得 2 個點數(shù)窜觉。總共獲得 6 個點數(shù)北专。

示例 2:

輸入:nums = [2,2,3,3,3,4]
輸出:9
解釋:
刪除 3 獲得 3 個點數(shù)竖螃,接著要刪除兩個 2 和 4 。
之后逗余,再次刪除 3 獲得 3 個點數(shù)特咆,再次刪除 3 獲得 3 個點數(shù)。
總共獲得 9 個點數(shù)录粱。

提示:

1 <= nums.length <= 2 * 104
1 <= nums[i] <= 104

分析:轉化為打家劫舍問題腻格,只不過這次不是根據數(shù)組下標決定狀態(tài)數(shù),而是根據數(shù)組中可能取到的最大值作為狀態(tài)數(shù)目啥繁。
題解:

class Solution:
    def deleteAndEarn(self, nums: List[int]) -> int:

        cnt = [0] * 10001

        for n in nums:
            cnt[n] += 1

        dp1 = 0
        dp2 = 0

        for i in range(0, len(cnt)):
            dp = max(dp2 + i * cnt[i], dp1)
            dp2 = dp1
            dp1 = dp

        return dp1

121. 買賣股票的最佳時機

題解:
方法一:轉化為求最大連續(xù)字串和問題

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        l = len(prices)
        new = [0] * l
        for i in range(1, l):
            new[i] = prices[i] - prices[i-1]

        init = new[0]
        ans = 0 
        for i in range(1, l):
            init = max(init + new[i], new[i])
            ans = max(ans, init)

        return ans

方法二:前綴最值角度

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        l = len(prices)
        prev_min = [0] * l
        prev_min[0] = prices[0]

        ans = 0

        for i in range(1, l):
            prev_min[i] = min(prev_min[i-1], prices[i])

            ans = max(ans, prices[i] - prev_min[i])

        return ans

1014. 最佳觀光組合

給你一個正整數(shù)數(shù)組 values菜职,其中 values[i] 表示第 i 個觀光景點的評分,并且兩個景點 i 和 j 之間的 距離 為 j - i旗闽。

一對景點(i < j)組成的觀光組合的得分為 values[i] + values[j] + i - j 酬核,也就是景點的評分之和 減去 它們兩者之間的距離。

返回一對觀光景點能取得的最高分适室。

示例 1:

輸入:values = [8,1,5,2,6]
輸出:11
解釋:i = 0, j = 2, values[i] + values[j] + i - j = 8 + 5 + 0 - 2 = 11

示例 2:

輸入:values = [1,2]
輸出:2

提示:

2 <= values.length <= 5 * 104
1 <= values[i] <= 1000

題解:
方法一:將最優(yōu)化目標拆成i和j的部分嫡意,再一次循環(huán)中j部分是固定的,我們只需要j前value[i] + i的最大項提前存起來即可捣辆。注意這里不能循環(huán)求解value[i] + i蔬螟,否則就是暴力窮舉了,時間復雜度不滿足要求

class Solution:
    def maxScoreSightseeingPair(self, values: List[int]) -> int:
        l = len(values)
        maxnum = 0
        left = values[0]
        for i in range(1, l):
            maxnum = max(values[i] - i + left, maxnum)
            left = max(values[i] + i, left)

        return maxnum

方法二: 狀態(tài)轉移:假設我們已知前一個節(jié)點 j 能組成的最大的組合為(i汽畴,j)旧巾, 那么緊接著的一個節(jié)點 j+1 最大得分的組合一定是(i耸序,j+1)和(j,j+1)這兩個組合中較大的一個鲁猩。

class Solution:
    def maxScoreSightseeingPair(self, values: List[int]) -> int:
        l = len(values)
        dp = [0] * l
        dp[0] = values[0]
        dp[1] = values[1] + values[0] - 1
        for i in range(2, l):
            dp[i] = max(values[i] + values[i-1] - 1, dp[i-1] + values[i] - values[i-1] - 1)

        return max(dp)

注意:對于抽象的問題要善于總結當前狀態(tài)與上一個狀態(tài)的聯(lián)系

1299. 將每個元素替換為右側最大元素

給你一個數(shù)組 arr 坎怪,請你將每個元素用它右邊最大的元素替換,如果是最后一個元素廓握,用 -1 替換芋忿。

完成所有替換操作后,請你返回這個數(shù)組疾棵。

示例 1:

輸入:arr = [17,18,5,4,6,1]
輸出:[18,6,6,6,1,-1]
解釋:
- 下標 0 的元素 --> 右側最大元素是下標 1 的元素 (18)
- 下標 1 的元素 --> 右側最大元素是下標 4 的元素 (6)
- 下標 2 的元素 --> 右側最大元素是下標 4 的元素 (6)
- 下標 3 的元素 --> 右側最大元素是下標 4 的元素 (6)
- 下標 4 的元素 --> 右側最大元素是下標 5 的元素 (1)
- 下標 5 的元素 --> 右側沒有其他元素戈钢,替換為 -1

示例 2:

輸入:arr = [400]
輸出:[-1]
解釋:下標 0 的元素右側沒有其他元素。

提示:

1 <= arr.length <= 104
1 <= arr[i] <= 105

題解:后綴最值問題

class Solution:
    def replaceElements(self, arr: List[int]) -> List[int]:
        l = len(arr)
        if l <= 1:
            return [-1]

        dp = [0] * l
        dp[-1] = -1
        for i in range(l-2, -1, -1):
            dp[i] = max(dp[i+1], arr[i+1])

        return dp
最后編輯于
?著作權歸作者所有,轉載或內容合作請聯(lián)系作者
  • 序言:七十年代末是尔,一起剝皮案震驚了整個濱河市殉了,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌拟枚,老刑警劉巖薪铜,帶你破解...
    沈念sama閱讀 212,294評論 6 493
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場離奇詭異恩溅,居然都是意外死亡隔箍,警方通過查閱死者的電腦和手機,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 90,493評論 3 385
  • 文/潘曉璐 我一進店門脚乡,熙熙樓的掌柜王于貴愁眉苦臉地迎上來蜒滩,“玉大人,你說我怎么就攤上這事奶稠「┘瑁” “怎么了?”我有些...
    開封第一講書人閱讀 157,790評論 0 348
  • 文/不壞的土叔 我叫張陵锌订,是天一觀的道長竹握。 經常有香客問我,道長辆飘,這世上最難降的妖魔是什么啦辐? 我笑而不...
    開封第一講書人閱讀 56,595評論 1 284
  • 正文 為了忘掉前任,我火速辦了婚禮蜈项,結果婚禮上芹关,老公的妹妹穿的比我還像新娘。我一直安慰自己战得,他們只是感情好充边,可當我...
    茶點故事閱讀 65,718評論 6 386
  • 文/花漫 我一把揭開白布庸推。 她就那樣靜靜地躺著常侦,像睡著了一般浇冰。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上聋亡,一...
    開封第一講書人閱讀 49,906評論 1 290
  • 那天肘习,我揣著相機與錄音,去河邊找鬼坡倔。 笑死漂佩,一個胖子當著我的面吹牛,可吹牛的內容都是我干的罪塔。 我是一名探鬼主播投蝉,決...
    沈念sama閱讀 39,053評論 3 410
  • 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場噩夢啊……” “哼征堪!你這毒婦竟也來了瘩缆?” 一聲冷哼從身側響起,我...
    開封第一講書人閱讀 37,797評論 0 268
  • 序言:老撾萬榮一對情侶失蹤佃蚜,失蹤者是張志新(化名)和其女友劉穎庸娱,沒想到半個月后,有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體谐算,經...
    沈念sama閱讀 44,250評論 1 303
  • 正文 獨居荒郊野嶺守林人離奇死亡熟尉,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內容為張勛視角 年9月15日...
    茶點故事閱讀 36,570評論 2 327
  • 正文 我和宋清朗相戀三年,在試婚紗的時候發(fā)現(xiàn)自己被綠了洲脂。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片斤儿。...
    茶點故事閱讀 38,711評論 1 341
  • 序言:一個原本活蹦亂跳的男人離奇死亡,死狀恐怖恐锦,靈堂內的尸體忽然破棺而出雇毫,到底是詐尸還是另有隱情,我是刑警寧澤踩蔚,帶...
    沈念sama閱讀 34,388評論 4 332
  • 正文 年R本政府宣布棚放,位于F島的核電站,受9級特大地震影響馅闽,放射性物質發(fā)生泄漏飘蚯。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點故事閱讀 40,018評論 3 316
  • 文/蒙蒙 一福也、第九天 我趴在偏房一處隱蔽的房頂上張望局骤。 院中可真熱鬧,春花似錦暴凑、人聲如沸峦甩。這莊子的主人今日做“春日...
    開封第一講書人閱讀 30,796評論 0 21
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽凯傲。三九已至犬辰,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間冰单,已是汗流浹背幌缝。 一陣腳步聲響...
    開封第一講書人閱讀 32,023評論 1 266
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留诫欠,地道東北人涵卵。 一個月前我還...
    沈念sama閱讀 46,461評論 2 360
  • 正文 我出身青樓,卻偏偏與公主長得像荒叼,于是被迫代替她去往敵國和親轿偎。 傳聞我的和親對象是個殘疾皇子,可洞房花燭夜當晚...
    茶點故事閱讀 43,595評論 2 350

推薦閱讀更多精彩內容