動態規劃專題總結

動態規劃專題

1連續子陣列的最大和（最大子序和）

輸入一個整型陣列nums，陣列里有正數也有負數，陣列中的一個或連續多個整陣列成一個子陣列，求所有子陣列的和的最大值，
定義dp[i]:　以nums[i]為結尾的子陣列的最大值

dp[i] = max(dp[i-1]+nums[i], nums[i])
以nums[i]為結尾的子陣列的最大值,要么是他自己（比如dp[i-1]是負數）,要么在前面子陣列的基礎上加上自己，形成更長的連續子陣列
記錄整個程序中的最大值，回傳該最大值（注意：dp[i]只是定義為以nums[i]為結尾的子陣列的最大值，所以dp[n-1]不一定是最大值），

2爬樓梯

假設你正在爬樓梯，需要n（n是一個正整數）階你才能到達樓頂. 每次可以爬 1 或 2 個臺階，有多少種不同的方法可以爬到樓頂
定義dp[i]:　爬完i階臺階共有dp[i]種方法

dp[i] = dp[i-1] + dp[i-2]
每次爬樓梯只有兩種方法，要么爬1個臺階，要么爬2個臺階，所以如果要爬到i級臺階，要么從i-1級臺階上爬1階上來，要么從i-2級臺階上爬2階上來
回傳dp[n]

3偷東西

小偷計劃偷竊沿街的房屋，每間房內都藏有一定的現金，影響偷竊的唯一制約因素就是相鄰的房屋裝有相互連通的防盜系統，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統會自動報警，給定一個代表每個房屋存放金額的非負整數陣列nums，計算在不觸動警報裝置的情況下，能夠偷竊到的最高金額
定義dp[i]:　"光顧"完前i個房屋后,能夠偷到的最高金額

dp[i] = max(dp[i-2]+nums[i], dp[i-1])
對于第i個房屋，有2種選擇，偷或不偷，偷：偷得的金錢加上"光顧"完i-2房屋時的偷竊金額，不偷：光顧"完i-1房屋的偷竊金額
回傳dp[n-1]

類似的題目:按摩師，在每次預約服務之間要有休息時間，因此不能接受相鄰的預約，求總預約時間最長

變種1：房屋不是一排，而是圍成了一個圈，也就是第一個房子和最后一個房子也是相鄰的，
計算2種情況：1）nums[0...n-2] 2）nums[1...n-1]，回傳兩者較大值即可，

變種2：房屋排列成二叉樹的形式，也就是父子節點上的房屋不能都偷竊，否則會報警，
用遞回解決，遞回函式的回傳值有兩個，第一個值是如果偷當前節點上的房子所獲取的最高金額，第二個值是如果不偷當前節點上的房子所獲取的最高金額，
主體偽代碼應該是這樣的：

left = func(root.left)
right = func(root.right)
steal = root.val + left[1] + right[1]
not_steal = max(left) + max(right)
或者這么寫：not_steal = max(left[0], left[1]) + max(right[0], right[1])
return steal, not_steal

4帶權爬樓梯

和爬樓梯問題類似，不過第i個階梯對應著一個非負數的體力花費值cost[i]，每當爬上一個階梯都要花費對應的體力花費值，爬的方式仍然是每次爬一個或者2個階梯，問到達到樓層頂部的最低花費，在開始時，可以選擇從索引為0或1的元素作為初始階梯
定義dp[i]: 如果第i層階梯就是樓層頂部，最低的花費，注意這種定義下：如果第i層階梯是目標樓層時，最后的花費是不包含cost[i]的，假設最后從第k層階梯爬上來，那么爬上第k層要花費對應的體力值cost[k]，然后從第k層直接1步或者2步來到樓層頂部(這里是第i層），或者這么理解：樓層頂部不是階梯，所以爬上樓層頂部沒有體力花費，

dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])
要么爬上第i-1個階梯，額外花費cost[i-1]，然后一步到達樓層，要么爬上第i-2個階梯，額外花費cost[i-2]，然后2步來到樓層，
最后回傳dp[n]

5網格中的路徑數

從m x n 網格的左上角走到網格的右下角，每次只能向下或者向右移動一步，問總共有多少條不同的路徑
定義dp[i][j]: 走到（i, j）時一共有多少條不同的路徑數

dp[i][j] = dp[i-1][j] + dp[i][j-1]
走到（i, j）只有兩種情況，要么從（i-1, j）向下移動一步，要么從（i, j-1）向右移動一步，
最后回傳dp[m-1][n-1]

變種：格子里有個權值，求最大值: dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + weight[i][j]
變種：求最小路徑和：dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + path[i][j]
變種:每一格都放有一個禮物，每個禮物都有一定的價值（價值大于 0）,最多能拿到多少價值的禮物
dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + grid[i][j]

6最大正方形

在一個由 0 和 1 組成的二維矩陣內，找到只包含 1 的最大正方形，并回傳其面積，
定義dp[i][j]: 以第（i, j）位置為右下角頂點的正方的最大邊長（前提當然是矩陣（i，j）位置處為1）

if matrix[i][j]==1: dp[i][j] = min(dp[i][j-1], dp[i-1][j-1], dp[i-1][j]) + 1
else: dp[i][j]=0

大家可以自己畫圖看看，以（ij）為右下角的正方形，能不能在原來的基礎上擴大邊長，主要取決于左邊、左上角、上邊這3個相鄰點的情況，且由最小的那個來決定，
在這個迭代的程序中，記錄最大的邊長，最后回傳邊長平方即可，
變種：還是0和1組成的二維矩陣，統計并回傳其中完全由 1 組成的正方形子矩陣的個數，正方形子矩陣可能包括邊長為1，邊長為2，邊長為i的正方形，那么可以定義dp[i][j]為以(i, j)為右下角的正方形的最大邊長，同時也可以表示以(i, j)為右下角的正方形的數目，假設dp[i][j]=3，即以(i, j)為右下角的正方形的最大邊長是3，那么以(i, j)為右下角的正方形共有3個，其邊長分別為3，2，1，

7最長公共子序列

給定兩個字串 str1 和 str2，回傳這兩個字串的最長公共子序列的長度（是子序列，不是連續子序列，比如“ab”是“acebad”的子序列）
定義dp[i][j]: str1[0...i]和str2[0...j]的最長公共子序列的長度，str1[0...i]表示str1中下標從0到i的這一段字串，

如果str1[i] == str[j]，則dp[i][j] = dp[i-1][j-1] + 1
否則dp[i][j] = max(dp[i-1][j], dp[i][j-1])

當str1[i] 與 str[j]不相等時，dp[i][j] = max(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])也是正確的，不過dp[i-1][j-1]一定小于等于dp[i-1][j]或者dp[i][j-1]（原因很好理解，無論dp[i-1][j]對應的字串str2[0...j]，還是dp[i][j-1]對應的字串str1[0...i]都比dp[i-1][j-1]對應的字串多一個字符，那么有且只有兩種可能，最長公共子序列長度加1，或者長度不變），所以可以省略以減少比較操作，
最后回傳dp[i-1][j-1]

8最小編輯距離

給定兩個字串 str1 和 str2，計算將 str1 轉換成 str2所使用的最少運算元，（可以使用3種操作：插入、洗掉、替換）
定義dp[i][j]: 將str1[0...i]轉換成str2[0...j]所使用的最少運算元，str1[0...i]表示str1中下標從0到i的這一段字串，

如果str1[i] == str[j]，則dp[i][j] = dp[i-1][j-1]
否則dp[i][j] = dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1

簡單解釋：
如果str1[i] == str[j]，無需操作，
否則：
1）把str1[i]替換成str2[j]，需要的運算元是dp[i-1][j-1]+1
2）洗掉字符str1[i]后，str1[0...i-1]等于str2[j]，需要的運算元是dp[i-1][j]+1
3）在str1[0...i]后面插入字符str2[j]后，str1[0...i]+str2[j]等于str2[0...j]，需要的運算元是dp[i][j-1]+1
最后回傳dp[n1][n2]（n1是str1的長度，n2是str2的長度）

9最長遞增子序列

給定一個無序的整數陣列nums，找到其中最長上升子序列的長度
定義dp[i]: 以nums[i]結尾的最長遞增子序列的長度

dp[i] = Math.max(dp[i], dp[j] + 1) ,0<=j<i and nums[j] < nums[i]
遍歷前面所有結尾比nums[i]小的子序列長度（把nums[i]加到最后，就形成了一個新的遞增子序列，長度在原來的基礎上加1），找最大的那個

最后回傳max(dp)

10最長回文子序列

給定一個字串s，找到其中最長的回文子序列，
定義dp[i][j]: 在子串 s[i..j] 中，最長回文子序列的長度

if s[i] == s[j]: dp[i][j] = dp[i+1][j-1] + 2
else: dp[i][j] = max(dp[i+1][j], dp[i][j-1])
如果s[i] 等于s[j]，那么把s[i]，s[j]分別加在s[i+1..j-1]兩側，形成新的更長的回文子序列，長度為原來長度加2
如果s[i] 不等于s[j]，那么把s[i]，s[j]分別加在s[i+1..j-1]兩側，一定無法形成新的且長度比原來長2的回文子序列，但是把s[j]加在s[i+1...j-1]右側，或者如果把s[i]加在s[i+1...j-1]左側，則有可能形成新的更長的回文子序列，

最后結果回傳dp[0][n-1]

11做菜順序

一個廚師收集了他 n 道菜的滿意程度 satisfaction ，這個廚師做出每道菜的時間都是 1 單位時間
一道菜的「喜愛時間」定義為烹飪這道菜以及之前每道菜所花費的時間乘以這道菜的滿意程度，也就是 time[i]*satisfaction[i]
回傳做完所有菜「喜愛時間」總和的最大值，可以按 任意 順序安排做菜的順序，也可以選擇放棄做某些菜來獲得更大的總和
定義dp[i][j]：前i個菜中選擇做j個菜的最大喜愛時間

if satisfaction[i] == satisfaction[j]: dp[i][j] = dp[i-1][j-1] + j*satisfaction[i-1]
else: dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]+j*satisfaction[i-1])
說明：首先需要對satisfaction 按從小到大排好序（相關證明略），下標0表示第一個菜，下標i-1表示第i個菜，
如果第i個菜放棄，則dp[i-1][j]，
如果選擇做第i個菜，那么這道菜的喜愛時間為j*satisfaction[i-1]，[j表示前面已做了j-1道菜，加上這道菜，花費了j單位時間]，加上之前的喜愛時間，就是dp[i-1][j-1]+j*satisfaction[i-1]，兩者取最大值，
最后結果回傳max(dp[len(satisfaction)])
這個問題用貪心效率更高，

12除數博弈

愛麗絲和鮑勃一起玩游戲，他們輪流行動，愛麗絲先手開局，
最初，黑板上有一個數字 N ，在每個玩家的回合，玩家需要執行以下操作：
選出任一 x，滿足 0 < x < N 且 N % x == 0 ，
用 N - x 替換黑板上的數字 N ，
如果玩家無法執行這些操作，就會輸掉游戲，
只有在愛麗絲在游戲中取得勝利時才回傳 True，否則回傳 false，假設兩個玩家都以最佳狀態參與游戲，
定義dp[i]： 黑板上數字是i的時候，先手的一方是必勝還是必敗（True表示先手必勝，False表示先手必敗）

dp[i] = True 如果存在一個x 且 dp[i-x]為False 且 i % x == 0 且 0<x<i
如果存在這樣一個x, 那么游戲開始時,愛麗絲先手,選取x. 然后留給鮑勃i-x, 這時輪到鮑勃先手,數字是i-x, 必敗,從而愛麗絲勝利

13三角形最小路徑和

給定一個三角形，找出自頂向下的最小路徑和，每一步只能移動到下一行中相鄰的結點上，相鄰的意思是下方或者右下方，
定義dp[i][j]： 走到（i,j）上的最小路徑和

dp[i][j] = min(dp[i-1][j], dp[i-1][j-1]) + triangle[i][j]

14最低票價

在一個火車旅行很受歡迎的國度，你提前一年計劃了一些火車旅行，在接下來的一年里，你要旅行的日子將以一個名為 days 的陣列給出，每一項是一個從 1 到 365 的整數，
火車票有三種不同的銷售方式：
一張為期一天的通行證售價為 costs[0] 美元；
一張為期七天的通行證售價為 costs[1] 美元；
一張為期三十天的通行證售價為 costs[2] 美元，
通行證允許數天無限制的旅行， 例如，如果我們在第 2 天獲得一張為期 7 天的通行證，那么我們可以連著旅行 7 天：第 2 天、第 3 天、第 4 天、第 5 天、第 6 天、第 7 天和第 8 天，回傳想要完成在給定的串列 days 中列出的每一天的旅行所需要的最低消費，
定義dp[i]：完成第i天時的最低消費

如果第i天是旅行的日子：dp[i] = min(dp[max(i-1,0)]+costs[0], dp[max(i-7,0)]+costs[1], dp[max(i-30,0)]+costs[2])
否則: dp[i] = dp[i-1]
第i天有4種狀態：a是不旅行的日子，消費保持不變；b花費一天的通行證，用以第i天的旅行；c利用前面某一天購買的7天通行證，第i天沒有花費；d利用前面某一天購買的30天通行證，第i天沒有花費，如果第i天是旅行的日子，那么最低消費一定是bcd中的最小值，
為什么？我們可以倒著想：假如x是最后一天旅行的日子，其花費的最小值取決于3個值，a第x-1天的花費+cost[0]（第x天買1天的通行證，第x天一定不需要買7天或者30天的通行證），b第x-7天的花費+cost1,c第x-30天的花費+cost[2]（第x-30+1天，也就是第x-29天，要買一張30天的通行證，從而第x天是這種通行證有效期內的最后一天），我們看第x-30天的花費：如果在第x-29天買一張30天的通行證，那么可以覆寫第x-30天以后的所有30天，且最后一天是第x天，也就是說如果第x天使用的是30天的通行證，那么第x-29天買是最劃算的，比如在第x-10天買，那么第x天的花費就是costs[2]+第x-11天的花費，而x-11>x-30，第x-11天的花費也一定大于等于x-30的花費（旅行的天數越多，花費也越多，當然也可能不變），同理可以分析x-7和x-1，從而得出第x天的花費只依賴第x-1天、第x-7天、第x-30天的花費，子問題找到，也就是狀態轉移的程序，

15股票系列

第 i 個元素表示股票第 i 天的價格

1. 如果你最多只允許完成一筆交易（即買入和賣出一支股票一次），設計一個演算法來計算你所能獲取的最大利潤
   定義dp[i]:第i天所能獲取的最大利潤

dp[i] = max(dp[i-1], prices[i]-buy_price), buy_price=min(buy_price, prices[i])
第i天,要么不交易,所獲利潤等于昨天的利潤dp[i-1], 要么賣出股票.使用buy_price記錄手中股票買入的最低價格

2. 如果可以無限次地完成交易，但是每筆交易都需要付手續費，如果你已經購買了一個股票，在賣出它之前你就不能再繼續購買股票了，求獲得利潤的最大值，
   dp[i][j] 表示第 i 天狀態為 j 時的最大收益，j只有0和1良好總取值, 0表示手中沒有股票,1表示手中持有股票

dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i] - fee);
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
優化空間以后:
tmp = profit_no_stock
profit_no_stock = max(profit_no_stock, profit_has_stock+prices[i]-fee)
profit_has_stock = max(profit_has_stock, tmp-prices[i])

16不同的二叉搜索樹

給定一個整數 n，求以 1 ... n 為節點組成的二叉搜索樹有多少種
定義dp[i]:長度為i的序列能構成的不同二叉搜索樹的個數

dp[i] += dp[j-1] * dp[i-j], 1<=j<=i
首先我們得知道,[1,2,3]這個長度為3的序列組構成的不同二叉搜索樹的個數,和[5,6,7]這個長度為3的序列組構成的不同二叉搜索樹的個數是一樣的,都是5個.也就是dp[i]和序列的內容無關，只和序列的長度有關.所以對于整數i,如果選j作為root, 則[1,...j-1]組成左子樹,序列長度為j-1(j-1個節點).[j+1,...,i]組成右子樹,序列長度為i-j(i-j個節點).那么以j為root的二叉搜索樹共有dp[j-1] * dp[i-j]個. j可選的范圍是[1,...,i],累加即可

17兩個字串的最小 ASCII 洗掉和

給定兩個字串s1, s2，找到使兩個字串相等所需洗掉字符的ASCII值的最小和
定義dp[i][j]: s1中前i個字符s1[0:i)和s2中前j個字符s2[0:j) 的最小和

dp[i+1][j+1] = min(dp[i][j+1]+ord(s1[i]), dp[i+1][j]+ord(s2[j])) 如果s1[i] != s2[j]
dp[i+1][j+1] = dp[i][j] 如果s1[i] == s2[j]
ord函式求字符的ascii值
如果當前字符不相等,那么刪去第i+1個字符(s1[i])變成子問題dp[i][j+1], 或者刪去第j+1個字符(s2[j]),變成子問題dp[i+1][j] ,取兩者最小值即可

標籤：其他

上一篇：藍橋杯 歷屆試題 螞蟻感冒

下一篇：序列化二叉樹