當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

算法训练营12-动态规划

發布時間：2024/2/28 编程问答 25 豆豆

生活随笔收集整理的這篇文章主要介紹了算法训练营12-动态规划小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

文章目錄

- 總結
- 題解
- - 1. 路徑問題
  - 2. 最長公共子序列
  - 3. 爬樓梯問題
  - 3. 三角形最小路徑和
  - 4. 最大連續子序列和
  - 5. 最小連續乘積
  - 6. 最少硬幣問題
  - 7. 打家劫舍
  - - 1. 解法一
    - 2. 解法二
  - 8. 打家劫舍2
  - 9. 買股票2

visited = set() dfs(self, node):if node in visited : return some// mark visited.add(node)// process currentprocess(node)// drill childfor n in node.child :self.dfs(n) from queue import Queue bfs( self, node ):if not node :return []que = Queue(node)res = []visited = set()while que :n = que.poll()if n not in visited :res.append(n)for child in n.child:que.offer(child)return res 遞歸 recursion(self,level, params):// recursion terminalif level > MAX_LEVEL :return // process logic in current levelprocess(params)// drill down self.recursion(level + 1, parmas2)// reverse the current level status if needed

題目

不同路徑題目
不同路徑 2 題目
最長公共子序列題目
MIT 動態規劃課程最短路徑算法

實戰題目
https://leetcode-cn.com/problems/climbing-stairs/description/
https://leetcode-cn.com/problems/triangle/description/
https://leetcode.com/problems/triangle/discuss/38735/Python-easy-to-understand-solutions-(top-down-bottom-up)
https://leetcode-cn.com/problems/maximum-subarray/
https://leetcode-cn.com/problems/maximum-product-subarray/description/
https://leetcode-cn.com/problems/coin-change/description/

https://leetcode-cn.com/problems/house-robber/
https://leetcode-cn.com/problems/house-robber-ii/description/
https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/#/description
https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/
https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/
https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/
https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv/
https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/
https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/solution/yi-ge-fang-fa-tuan-mie-6-dao-gu-piao-wen-ti-by-l-3/

課后作業
https://leetcode-cn.com/problems/longest-valid-parentheses/
https://leetcode-cn.com/problems/minimum-path-sum/
https://leetcode-cn.com/problems/edit-distance/
https://leetcode-cn.com/problems/decode-ways
https://leetcode-cn.com/problems/maximal-square/
https://leetcode-cn.com/problems/max-sum-of-rectangle-no-larger-than-k/
https://leetcode-cn.com/problems/frog-jump/
https://leetcode-cn.com/problems/split-array-largest-sum
https://leetcode-cn.com/problems/student-attendance-record-ii/
https://leetcode-cn.com/problems/task-scheduler/
https://leetcode-cn.com/problems/palindromic-substrings/
https://leetcode-cn.com/problems/minimum-window-substring/
https://leetcode-cn.com/problems/burst-balloons/

總結

三個過程一定要整清楚

dp表的下標和初始值要考慮清楚，不能出現使用錯誤的情況

dp的基本思路要熟練，更復雜的問題，并不dp復雜，而是狀態dp方程的可能性比較多，dp方程不容易搞，比如正則匹配的那種

題解

1. 路徑問題

class Solution:def uniquePaths(self, m: int, n: int) -> int:step = [1] * nfor i in range(1,m):for j in range(1,n):step[j] += step[j-1]return step[n-1]# 問題分解 problem(i,j) = sub_problem(i,j-1) + sub_proble(i-1, j)，這里的問題的思考思路和視頻中不一致， # 而是直接從終點開始劃分的，這樣遞推方程邏輯和子問題邏輯保持了一致性 # 狀態 row,col,count_step # 狀態轉移方程 f(i,j) = f(i,j-1) + f(i-1,j)# 把問題的規模和狀態轉移方程分開來看，可能會有助于解決問題, # 同時，如果問題的分解方式和狀態轉移方程能夠保持一致性的邏輯的話，則有助于問題的解決 # 判斷一個問題的時候，有可能只是簡單的邏輯型的題，不需要分治遞歸等處理方式，這個時候只要按照邏輯進行處理即可 # 有可能這個題是一個稍微復雜的問題，這個時候可以試試是否可以通過分治解決 # 如果可以通過分治解決，判斷是否有重復的子問題，沒有的話就是分治或者回溯型問題，有的話基本上就要使用動態規劃來解決了 # 先進行問題分解 # 找狀態 # 推算遞推方程，盡可能滿足和問題分解的方式是一樣的，有些時候可能會把看問題的角度顛倒過來，為了結果的得出更方便，比如三角形的最短路徑問題，但是使用從最簡單的問題，到規模更大的依然是可以的 # 字符串問題，常常在劃分子問題的時候從末尾開始，也是為了和遞推方程保持更好的logic一致性

2. 最長公共子序列

數組的下標需要特別注意才行

# 問題劃分： problem(s1[i:],s2[j:]) = # 1. if s1[i] = s2[j] => 1 + sub_prob(s1[i+1:],s2[j+1:]) # 2. if s1[i] != s2[j] => max( sub_prob(s1[i+1:],s2[j]), sub_prob(s1[i:],s2[j+1:])) # 通過問題劃分為子問題，可以看到子問題之間是有重復子問題的，所以這不是一個完全的分治，而是一個動態規劃， # 所以要找狀態和狀態轉移方程了# 狀態 len_count, sub_s1, sub_s2 # 狀態轉移方程這個時候如果使用上面的可以看出來狀態方程沒有辦法寫了，那么這個時候可以試著把問題逆過來看，也就是字符串從后面開始比較和匹配，更有利于寫出狀態方程， # 其實從上面的方式，我們也是可以寫出狀態轉移方程，使用緩存的方式是可以解決的，但是想要使用dp table推算就比較困難了 # 轉化問題求解思路，從后面開始匹配 # 問題劃分： problem(s1[:i],s2[:j]) = # 1. if s1[i] = s2[j] => 1 + sub_prob(s1[:i-1],s2[:j-1]) # 2. if s1[i] != s2[j] => max( sub_prob(s1[:i-1],s2[j]), sub_prob(s1[:i],s2[:j-1]))# 狀態 len_count, sub_s1, sub_s2 # 狀態轉移方程，這個時候感覺順多了，既可以認為是把問題劃分是一樣的，這樣的話dp,table的方式也就好做了 # 加緩存的方式，因為字符串反復拷貝，沒有通過內存校驗 class Solution:def __init__(self):self.dic = {}def longestCommonSubsequence(self, text1: str, text2: str) -> int:return self.recursion_count(text1,text2)def recursion_count(self,text1,text2):if not text1 or not text2 :return 0key=text1+"_"+text2if key in self.dic :return self.dic[key]else:if text1[:1] == text2[:1]:self.dic[key] = 1+self.recursion_count(text1[1:],text2[1:])else :self.dic[key] = max(self.recursion_count(text1[1:],text2),self.recursion_count(text1,text2[1:]))return self.dic[key] # dp table 模式 # 數組的下標需要特別注意才行class Solution:def longestCommonSubsequence(self, text1: str, text2: str) -> int:len01 = len(text1)len02 = len(text2)dp = [[0] * (len01+1) for _ in range(len02+1)]for row in range(1,len02+1):for col in range(1,len01+1):if text1[col-1:col] == text2[row-1:row]: # 這里最開始搞錯了，沒有-1dp[row][col]=1+dp[row-1][col-1]else :dp[row][col] = max(dp[row][col-1],dp[row-1][col])return dp[len02][len01]

3. 爬樓梯問題

class Solution:def climbStairs(self, n: int) -> int:a=1b=2if n<3:return nfor i in range(3,n+1):temp = bb += aa = tempreturn b# 子問題： prob(n) = prob(n-1) + prob(n-2), 有重復子問題，所以是動態規劃 # 狀態：當前階梯數，返回走到當前的方法數 # 狀態轉移方程 f(n) = f(n-1) + f(n-2)

3. 三角形最小路徑和

這個題，是比較典型的題目，兩種解法對比有益于開拓思路

第一種解法，需要注意，問題有時候看似可以用某種模式解決，但是實際上解決起來又很困難，這個時候可能需要將問題進行轉換才行，可能是用空間升維一下試試，說不定就豁然開朗了
還有就是有些時候邊界處理是不可避免的，需要加上

class Solution:def minimumTotal(self, triangle: List[List[int]]) -> int:row_num = len(triangle)dp = [0]*row_numdp[0] = triangle[0][0]for level in range(1,row_num):print(dp[0])for pos in reversed(range(0,level+1)):if pos == 0:dp[0] += triangle[level][0]elif pos == level: # 最開始這個邊界問題還是沒有帶上dp[pos] = dp[pos-1]+triangle[level][pos]else:dp[pos]=min(dp[pos-1],dp[pos])+triangle[level][pos]print(dp)return min(dp) # 暴力使用深度優先遍歷可以拿到 # 分治方法 # 問題劃分：可以嘗試減小一層試試，也就是到達第n層和到達第n-1層之間的關系 problen(n) = min(posible_sub_proble(n-1)+path[n][k]),這個感覺還比較復雜，當然可以類比路徑的題目，很相似，就是走路的方式變了,感覺很難表達，需要升維了啊，要搞清狀態的維度，之所以難以表達，可能就是維度沒有整對， # 升維，編程二維 problem(n) = min(proble(n,k)){k=>0-k} # problem(n, i)=min(proble(n-1,i), proble(n-1,i-1))+weight[i] # 狀態： dp[row][col] 到達col的最小路徑 # # 狀態轉移方程: f(n) = min(f(n,k)) {k=>0-k} # f(n,k) = min(f(n-1,k),f(n-1,k-1)) + weight[k] # # 總結來說，還是問題沒有弄對，直接對著題目的目標開干了，觀察我們的狀態轉移方程發現其實問題被我們轉換成了： # 從開始點到任意一個點的最短路徑+ 最后一層求min兩個階段的問題了，所以有時候迭代的主邏輯只處理了一部分問題，要注意這種轉換思路 # 問題的目標有時候并不一定直接能夠通過某種模式達到，可能需要一些問題形式的轉換 #

第二種思考方式

## 第二種思考方式 # 問題的子問題劃分： problem(0->n)= min(sub(1->n)+weight[k]),這里雖然勉強完成了抽象，但是也是不是很清晰， # 就是從第0層到最下面一層等于從第二層到最下面的加上第一層和第二層的和，這種，但是還是要繼續抽象才行,還是要變成二維才能合理表達 # problem(level->n,i) = min(sub(level+1->n,i)+weiht[i],sub(level+1->n,i+1)+weiht[i+1]) # 狀態： dp[level][i] 值為這一步到最底層的最小值 # 狀態轉移方程：同子問題劃分 # 這個思考方式和上面的很不同，算是自頂向下的思考方式，上面的算是自底向上的思考方式,包括之前的路徑問題也是一樣的， # 就是第一題，也有兩種思路求解，所以以后的話可以看哪種對計算結果更加有利，就使用哪種,這種明顯更優，邊界處理也不需要了class Solution:def minimumTotal(self, triangle: List[List[int]]) -> int:row_num = len(triangle)dp = [0]*row_numfor i in range(row_num):dp[i]=triangle[row_num-1][i]for level in reversed(range(0,row_num-1)):for pos in range(0,level+1):dp[pos]=min(dp[pos],dp[pos+1])+triangle[level][pos]print(dp)return dp[0]

4. 最大連續子序列和

# 1. 暴力法，枚舉start,end # 2. 嘗試分解子問題 # 子問題劃分：problem(n)=max(sub(n-1),nums[n]+) # 狀態： # 狀態轉移方程： # 分解了半天，啥也沒有分解出來，因為這個問題也要轉化才行，啊啊啊，感覺這個題比路徑的題還難，之前使用找規律做出來過，現在不行了 # 這個如果強行劃分子問題的話是劃分不出來的，因為problem(n)和proble(n-1)之間實際上是沒有關系的， # 因為有可能在problem中就沒有選擇第n-1個元素，這樣的話想要轉化為p(n)=max(p(n-1)+nums[n-1],nums[n-1])也是不行的， # 因為p(n-1)+nums[n-1]這個狀態是不合法的，我想了好幾分鐘沒有想出來，看題解看了好一會兒，哭泣 # 這個時候想著怎么轉化問題，能讓p(n-1)+nums[n-1]是一個合法的狀態呢，問題就轉化為p(n-1)代表了必須算進去n-1, 也就是把問題轉化為 # p(k)代表了以k作為結尾的最大連續子序列，我們的問題是求max{p(k)} k->(0,n-1),這樣的話才能使用動態規劃， # 感覺就是把問題轉化為了可以枚舉的狀態# 在上面的思路上，我們就可以快樂的球p(k)了，然后再求最大的p(k)就是結果 # 問題分治(轉換之后的問題)：p(n)=max(sub(n-1)+nums[n],nums[n]) # 狀態：：dp[n]，代表以n結尾的連續子串的最大和 # 狀態轉移方程 f(n)=max(f(n-1)+nums[n],nums[n])class Solution:def maxSubArray(self, nums: List[int]) -> int:max_res = nums[0]pre = nums[0]for i in range(1,len(nums)):cur_max = max(pre + nums[i],nums[i])max_res = max(cur_max,max_res)pre = cur_maxreturn max_res

5. 最小連續乘積

class Solution:def maxProduct(self, nums: List[int]) -> int:max_res = nums[0] neg_res = nums[0]pre_max = nums[0]pre_neg = nums[0]for i in range(1,len(nums)):if nums[i] > 0:cur_max = max(pre_max * nums[i],nums[i])cur_neg = min(pre_neg * nums[i],nums[i])else :cur_max = max(pre_neg * nums[i],nums[i])cur_neg = min(pre_max * nums[i],nums[i])pre_max = cur_maxpre_neg = cur_negmax_res = max(cur_max,max_res)return max_res # 這一題類似上一題，乘積，需要考慮負數整數 # 1. 暴力，枚舉start,end # 2. 想著分解問題 # 問題分解：先轉化問題，轉化為在以k (k => 0->n)結尾的子序列中找最佳結果 p(k) 代表了以k結尾的子序列的最大乘積 # 那么可以有prob(n)=max(prob(n-1)*nums[n], nums[n]),同時，需要考慮的是有可能出現負值，還所以prob(k)需要輸出兩個值，一個是負值，一個正值，所以需要升維 # 再轉為: # nums[n]為正,因為必須有一個元素，所以最小值可能是正的，是為了給后面的使用 # prob(n,負值)=min(prob(n-1,負值)*nums[n],nums[n]) prob(n,正值)=max(prob(n-1,正值)*nums[n],nums[n]) # nums[n]為負值 # prob(n,負值)=min(prob(n-1,正值)*nums[n],nums[n]), prob(n,正值)=max(prob(n-1,負值)*nums[n],nums[n]) # 因為問題中有重復子問題，所以考慮動態規劃 # 狀態：dp[i] table 中每個元素存儲最大最小兩個值 # dp方程：同子問題轉化 # 格局dp table得出最優解

6. 最少硬幣問題

從這個問題的對比思考，發現問題的轉換模式有時候需要注意的是，有些子問題是有序的，比如問題的模型數數組類型的或者是字符串類型的那種，有些則是動態的，比如現在這種，對于不同的問題，轉換思路也是不一樣的，這個問題基本上不需要對原問題進行轉換

class Solution:def coinChange(self, coins: List[int], amount: int) -> int:dp = [(amount+1)]* (amount+1)dp[0] = 0for am in range(amount+1):for aConin in coins :if am >= aConin :dp[am] = min(dp[am],dp[am-aConin]+1)if dp[amount] > amount :return -1else :return dp[amount]# 暴力，可以做成一個樹的回溯型遍歷 # 嘗試分治 # 問題分解：這個思考的方式是假如選擇了去了一個硬幣(不用思考為像路徑問題一樣非要是最后一次裝進去的硬幣，就可以是第一次裝進去的硬幣)， # 這里優先考慮的就是劃分為子問題，先不用想狀態方程相關的，這里的問題的因子有連個，一個是amount,一個是conins, # 所以 prob(amount,conins)=min(prob(amount-conins[i], conins))+1 i=>(0,k) 也就是硬幣可以選擇任意一個# 狀態 : dp[amount] 表示在這個amount下的使用的硬幣的最小數目 # 狀態轉移方程：因為conins是每次都有的，所以可以忽略 f(amount)=min(f(amount-conins[i]))+1 ; i=>(0,k) # # 這個問題還有一個關鍵是有可能找不到答案，需要返回-1，如何設計dp table來表示最后沒有答案也是一個技巧， # 這里是dp[amount]都初始化為amount+1,比較巧妙 # # 同時，這個問題更復雜的是如何初始化初始狀態，這點也很重要，不像字符串等邏輯比較簡單， # 這里是不等于判斷，相對邏輯更加復雜，而且初始化也要動態執行下面是記憶化遞歸的模式 class Solution:def coinChange(self, coins: List[int], amount: int) -> int:self.mem = [-1] * (amount+1)self.mark = amount + 1res = self.recusionCoin(coins,amount)if res > amount :return -1 else :return res def recusionCoin(self,coins,amount):if amount == 0 :return 0 if amount < coins[0]:return self.markif self.mem[amount] >= 0 :return self.mem[amount]cur_min = self.markfor co in coins :subAmount = amount - co if subAmount >= 0 :cur_min = min(cur_min,self.recusionCoin(coins,subAmount)+1)return cur_min

7. 打家劫舍

1. 解法一

這個解法是自己創造的一個理解角度，也是挺有意思的，哈哈哈

class Solution:def rob(self, nums: List[int]) -> int:if len(nums)==0:return 0dp = [0] * (len(nums) + 1)if len(nums) <= 2 :return max(nums)dp[0] = nums[0]dp[1] = nums[1]dp[2] = dp[0]+nums[2]res_max = max(dp[2],dp[1])for i in range(3,len(nums)):dp[i] = max(dp[i-2],dp[i-3])+nums[i]res_max = max(res_max,dp[i])return res_max# 暴力 1. 可以深度遍歷或者排列組合的方式，每一個選或者不選 # 問題分解 # 分解為子問題：當我看到這個問題的時候，想到了上次的最大連續子序列的問題，想到的是把問題轉化，轉化為求解prob(n) = max(another_prob(k)) k=>(1->n) ,another_prob(k)是指總共有k個房間，且第k個必須偷能夠得到的最大值的子問題，這就等于是把原來的問題枚舉了，因為不管最優解是啥，那么最優解肯定是以某個i必偷為結尾的，現在回過頭來想想，這個思路反而是比較難以想到的，但是代碼確實簡單了。等于把不可枚舉的問題轉化為可以枚舉的了。那么another_prob之間的關系是 aprob(n)=max(aprob(n-2)+nums[n],aprob(n-3)+nums[n]),其實這里應該是還有aprob(n-4)等等一直到1的，但是可以推算有這兩個就足夠了，可以包含所有的最優解 # 狀態： dp[i] 存儲的是對應的以i結尾的最優解 # 狀態轉移方程： dp[i]=max(dp[i-2],dp[i-3])+nums[i]

2. 解法二

這個其實就是問題的本源，一開始也是想要這樣思考的，但是因為擔心sub_prob(n-1)和sub_prob(n-2)可能有重復而導致了猶豫，實際上是不影響的，即使有重復問題那么這個解的邏輯是正確的就行

class Solution:def rob(self, nums: List[int]) -> int:if len(nums)==0:return 0dp = [0] * (len(nums))if len(nums) <= 2 :return max(nums)dp[0] = nums[0]dp[1] = max(nums[1],nums[0])for i in range(2,len(nums)):dp[i] = max(dp[i-1],dp[i-2]+nums[i])return dp[-1]# 問題分解 # 子問題劃分： prob(n) 可以分為兩種情況，第一種是沒有選擇nums[n] 進行搶劫這個時候prob(n)=sub_prob(n-1)，第二種是搶劫了nums[n],這個時候prob(n)=sub_prob(n-2)+nums[i], 其中sub_prob(n-1)和sub_prob(n-2)可能有重復，但是對于本題的解沒有影響，這個也是對于有序問題的解法，關注順序，和上面的硬幣是兩個類型的問題，因為子問題是有重復的，所以可以使用動態規劃 # 狀態：dp[i] 長度為i的序列，得到的最大值 # 狀態轉移方程：f(i)=max(f(i-1),f(i-2)+nums[i])

8. 打家劫舍2

把原始的問題轉化為了兩個獨立的dp問題，有時候問題要轉化為可以枚舉結果的子問題，讓后這些子問題是可以通過dp來解決的
感覺dp問題比較牛叉的一點在于不怕重復子問題，通過這種遞推解題，真是過癮

class Solution:def rob(self, nums: List[int]) -> int:if len(nums)<= 2:return max(nums)dp = [[0]*len(nums) for _ in range(2)]dp[0][0] = nums[0]dp[1][0] = 0dp[0][1] = max(nums[0],nums[1])dp[1][1] = nums[1]for i in range(2,len(nums)-1):dp[0][i] = max(dp[0][i-1] , dp[0][i-2] + nums[i])dp[1][i] = max(dp[1][i-1] , dp[1][i-2] + nums[i])return max(dp[0][len(nums)-2],dp[1][len(nums)-3]+nums[-1])# 這個問題，想起來就覺得頭大，可以這樣分解，實際上也是在問題一上的借鑒，假如沒有問題一的話，不知道還行不行呢 # 劃分子問題如果最后一個元素不選的話則 prob(n)=prob(n-1)和上一個題解答一樣，如果最后最后一個元素選擇了的話，則第一個肯定不能選了，問題就變成了prob(n)=prob(n-2,nums[1:n])+nums[n]了，可以看到，實際上這里的參數也發生了變化，這個時候，問題的變量也變了，所以需要升維才能解決了，需要兩個一維數組，一個保留nums，所以這個其實也是問題轉化，把原始的問題轉化為了兩個獨立的dp問題，然后綜合這兩個獨立的dp問題的結果來得到最后的結果 # 狀態 dp01[i]:標識在包含0位置的情況下最優的值， dp02[i]:標識在不包含0位置的元素下求解的值 # 狀態轉移方程 f(0,n)=max(f(0,n-1),f(1,n-2)+nums[i]) f(0,n-1)的求解就轉化為了原來的問題，f(1,n-2)的求解也轉化為了原來的問題，原來的狀態方程就是f(i)=max(f(i-1),f(i-2)+nums[i])最終再總結一下就行了

9. 買股票2

class Solution:def maxProfit(self, prices: List[int]) -> int:res = 0 for i in range(len(prices)-1) :if prices[i] < prices[i+1] :res += prices[i+1]-prices[i]return res class Solution:def maxProfit(self, prices: List[int]) -> int:dp = [[0]*len(prices) for _ in range(2)]dp[0][0] = 0dp[1][0] = -prices[0]for i in range(1,len(prices)) :dp[0][i] = max(dp[0][i-1],dp[1][i-1]+prices[i])dp[1][i] = max(dp[0][i-1]-prices[i],dp[1][i-1])return dp[0][-1]## 解法一：貪婪算法，這種其實很難想到 ## 解法二：嘗試分解子問題 # 如果第n天沒有發生賣掉行為，則prob(n)=prob(n-1) 如果發生了賣掉行為prob(n),則前一天必須是持股的狀態，同時還有買入行為也要記賬，感覺這個問題的思路沒有清理清楚， # 總的來說，是因為這個問題的變量啥的比較多，也就是狀態比較多，沒有搞清楚，在劃分為子問題的時候，需要先弄清楚需要定義哪些狀態更合適 # 上面把操作定義成了狀態，也就是買和賣，但是實際上狀態應該是是否持有股票，這樣可能就比較清晰了，狀態轉化是買和賣 # 感覺這個問題和前面做的問題還不太一樣，前面的都是比較好定義狀態，狀態大部分就是問題的解，或者是問題轉換之后的子問題的解， # 這里如果直接把狀態定義為第i天的利潤，因為牽扯到賣掉賣掉，這樣就還要考慮到前一天是否持有股票， # 所以要增加一個狀態，標識股票的持有狀態 # 這個典型的是通過操作轉化狀態，其實之前的題也是，轉化為子問題，總是有一些操作的， # 我們可以把狀態的轉化視為操作，比如選擇一個硬幣，比如字符串中先對一個字符進行匹配，比如最后一家搶或者不搶，這些都是操作 # 定義了合適的狀態，操作才會顯得順利，狀態中沒有是否持有股票的話，那么操作中也就無法談買和賣啊，娃子， # 也就是說定義子問題和定義狀態，有時候是相輔相成的，沒有好的狀態，也很難劃分子問題，而且有時候子問題可能有多種狀態， # 也就是在多個子問題中轉換，這時候就需要升級維度來滿足## 解法重寫 # 子問題劃分第i天的利潤可以劃分為第i天要執行賣操作或者是無操作，但是如果i是中間的一天的話，可能還有買操作， # 這也是這個問題困難的地方，最后一天的狀態和中間的某一天的狀態是不一樣的 # 假設最后一天有賣和不操作兩個狀態，那么對應的對前一天就有要求是否持有股票的要求， # 那么這個時候可以暫停一下子問題的劃分過程，看看是不是應該升維來增加一個對狀態的標識了， # 這個也是將原有問題轉化的一個過程，是不是可以和上面的最大和連續子序列上的轉化做類比呢？ # 假如把問題轉化一下，就是prob(n),轉化為max(prob(持有股票,n)， prob(不持有股票,n)),替換為max(prob(0,n),prob(1,n)) # prob(0,n)=max(prob(1,n-1)+prices[n], prob(0,n-1)) prob(1,n)=max(prob(0,n-1)-prices[i], prob(1,n-1)) # # 狀態： dp[0][i] dp[1][i] dp[0][i]標識第i天結束之后沒有股票，這個時候的最大利潤是 dp[1][i]是第i天結束后有股票的最大利潤# 狀態轉移方程：和子問題轉換過程基本一致

總結

以上是生活随笔為你收集整理的算法训练营12-动态规划的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。