動態規劃思想

動態規劃（Dynamicprogramming）是一種通過把原問題分解為相對簡單的子問題的方式求解復雜問題的方法。
動態規劃常常適用于有重疊子問題和最優子結構性質的問題，動態規劃方法所耗時間往往遠少于樸素解法。
動態規劃背后的基本思想非常簡單。大致上，若要解一個給定問題，我們需要解其不同部分（即子問題），再合并子問題的解以得出原問題的解。
通常許多子問題非常相似，為此動態規劃法試圖僅僅解決每個子問題一次，從而減少計算量：一旦某個給定子問題的解已經算出，則將其記憶化存儲，以便下次需要同一個子問題解之時直接查表。這種做法在重復子問題的數目關于輸入的規模呈指數增長時特別有用。

動態規劃算例

**算例1
來源個人其他博文
leetcode解碼方法（動態規劃python）
描述

有一個消息包含A-Z通過以下規則編碼

‘A’ -> 1
‘B’ -> 2
…
‘Z’ -> 26
現在給你一個加密過后的消息，問有幾種解碼的方式

我們不能解碼空串，因此若消息為空，你應該返回0。
消息的長度 n \leq 100n≤100

您在真實的面試中是否遇到過這個題？
樣例
樣例 1:

輸入: “12”
輸出: 2
解釋: 它可以被解碼為 AB (1 2) 或 L (12).
樣例 2:

輸入: “10”
輸出: 1

思路
動態規劃，從s的位置1讀起，每次讀取兩個數，因為只要是1-9的數，都可以單獨出現，因此，dp表可以初始化為1，為了避免第二個條件[i-1]無法執行，我們使得dp表從位置2開始修改，dp位置0，1的值都初始化為1

情況
#特殊情況 輸入’’ 則無法解碼，可直接返回 0
#輸入0 則無法解碼，可直接返回 0
#若為 00 或 30、40、50… 則無法解碼，可直接返回 0
#為 10、20 的情況，則 i 處字符必須與前一位結合，則為雙字符解碼
dp[i + 1] = dp[i - 1]
若數字為10-26：既可以單字解碼，又可以雙字解碼 dp[i + 1] = dp[i] + dp[i - 1]
#1-9，27-29、31-39、41~49…只能單字解碼 dp[i + 1] = dp[i]

class Solution:def numDecodings(self, s):if len(s)==0: return 0 #特殊情況 輸入'' 則無法解碼，可直接返回 0if s[0]=="0":return 0 #輸入0 則無法解碼，可直接返回 0dp = [0] * (len(s) + 1)dp[0],dp[1]=1,1for i in range(1, len(s)):if s[i] == '0':if int(s[i - 1]) > 2 or int(s[i - 1]) == 0: #若為 00 或 30、40、50... 則無法解碼，可直接返回 0；return 0dp[i + 1] = dp[i - 1] #為 10、20 的情況，則 i 處字符必須與前一位結合，則為雙字符解碼elif 9 < int(s[i - 1:i + 1]) < 27:dp[i + 1] = dp[i] + dp[i - 1] #既可以單字解碼，又可以雙字解碼else:dp[i + 1] = dp[i]#1-9，27~29、31~39、41~49....只能單字解碼return dp[-1] test = Solution() s_li = ["9", "226", "300"] for s in s_li:print(test.numDecodings(s))

算例2：

來源個人博文
leetcode最大矩形 (動態規劃 python)

描述

給你一個二維矩陣，權值為False和True，找到一個最大的矩形，使得里面的值全部為True，輸出它的面積

您在真實的面試中是否遇到過這個題？
樣例
樣例1

輸入:
[
[1, 1, 0, 0, 1],
[0, 1, 0, 0, 1],
[0, 0, 1, 1, 1],
[0, 0, 1, 1, 1],
[0, 0, 0, 0, 1]
]
輸出: 6
樣例2

輸入:
[
[0,0],
[0,0]
]
輸出: 0

解題思路

假設我們輸入的矩形第一行數時是：
[1, 1, 1, 0, 1,1，0,1,1]
我們統計這行的最大寬度:
得到數組a如下：
a=1,2,3,0,1,2,0,1,2]

正式解題：
1.輸入矩形
[
[1, 1, 0, 0, 1],
[0, 1, 0, 0, 1],
[0, 0, 1, 1, 1],
[0, 0, 1, 1, 1],
[0, 0, 0, 0, 1]
]
maxarea=0
2.然后對矩形的第一行統計最大寬度
得到寬度數組：
[1,2,0,0,1]
計算最大面積=2
更新maxarea
3.然后對矩形的第二行統計最大寬度：
得到寬度數組：
[0, 1, 0, 0, 1]
計算面積：分兩步
第一步：計算當前寬度數組最大面積為1 如果大于maxarea 則更新maxarea
第二步 ：計算當前寬度數組和上一寬度數組產生的最大面積：
最大面積應為同一列數的（最小值） 乘以 （行數）
結果為1乘以2=2
如果大于maxarea 則更新maxarea
4.然后對矩形的第三行統計最大寬度：
得到寬度數組[0, 0, 1, 1, 1]
在計算這行產生的最大面積時。
第一步只把第三行寬度數組，計算只有第三行寬度度數組產生的最大面積：結果1 如果大于maxarea 則更新maxarea
第二步： 計算（第三行寬度數組，第二行寬度數組）最大面積 2
如果大于maxarea 則更新maxarea
第三步：最后在計算（第三行寬度數組，第二行寬度數組 ，第一行寬度數組）的最大面積。如果大于maxarea 則更新maxarea

后面類似：

整個過程應該是個動態：
代碼如下：

lass Solution:def maxmalRectangle(self , matrix):m = len(matrix)n = len(matrix[0])maxarea = 0dp = [[0]*n for _ in range(m)]for i in range(m):#遍歷每一列for j in range(n):#遍歷每一行if matrix[i][j] == 0:continuewidth = dp[i][j] = dp[i][j-1] + 1 if j else 1#計算最大寬度并使用它更新dpfor k in range(i,-1,-1):#倒序遍歷每一行width = min(width , dp[k][j])#最小寬度（同一列 上下幾行的最小【最大寬度】）maxarea = max(maxarea , width*(i - k + 1)) #同一列上下幾行的最小【最大寬度】*行數=當前行最大面積return maxarea test = Solution() d=test.maxmalRectangle([[1, 1, 0, 0, 1],[0, 1, 0, 0, 1],[0, 0, 1, 1, 1],[0, 0, 1, 1, 1],[0, 0, 0, 0, 1] ]) print(d)

算例3
來源于個人博客
LeetCode最大子序和 （動態規劃）python
描述
給定一個整數數組，找到一個具有最大和的子數組，返回其最大和。

子數組最少包含一個數

您在真實的面試中是否遇到過這個題？
樣例
樣例1:

輸入：[?2,2,?3,4,?1,2,1,?5,3]
輸出：6
解釋：符合要求的子數組為[4,?1,2,1]，其最大和為 6。
樣例2:

輸入：[1,2,3,4]
輸出：10
解釋：符合要求的子數組為[1,2,3,4]，其最大和為 10。

思路 動態規劃
設sum[i]為以第i個元素結尾的最大的連續子數組的和。假設對于元素i，所有以它前面的元素結尾的子數組的長度都已經求得，那么以第i個元素結尾且和最大的連續子數組實際上，要么是以第i-1個元素結尾且和最大的連續子數組加上這個元素，要么是只包含第i個元素，即sum[i]= max(sum[i-1] + a[i], a[i])。可以通過判斷sum[i-1] + a[i]是否大于a[i]來做選擇。因為中間有的sum[i]已經領過加負值變為0啦，后面的sum[i]求和就得根據后面新的數重新計算。 所以最大子序和就是sum[]數組的最大值

代碼1

class Solution:"""@param nums: A list of integers@return: A integer indicate the sum of max subarray"""def maxSubArray(self, nums):# write your code herelength=len(nums) if length==0:return 0for i in range(1,length): #當前值的大小與前面的值之和比較，若當前值更大，則取當前值，舍棄前面的值之和 MaxSum=max(nums[i]+nums[i-1],nums[i]) nums[i]=MaxSum#將當前和最大的賦給nums[i]，新的nums存儲的為和值 return max(nums) nums=[-2,2,-3,4,-1,2,1,-5,3]c=Solution() d=c.maxSubArray(nums) print(d)

代碼2：

class Solution:"""@param nums: A list of integers@return: A integer indicate the sum of max subarray"""def maxSubArray(self, nums):# write your code hereif len(nums)==0:return 0presum=maxsum=nums[0]#presum當前和，maxsum最好的和for i in range(1,len(nums)):presum=max(presum+nums[i],nums[i])maxsum=max(maxsum,presum)return maxsumnums=[-2,2,-3,4,-1,2,1,-5,3]c=Solution() d=c.maxSubArray(nums) print(d)

算例4
來源于個人博客
LeetCode 392打劫房屋 python
描述
假設你是一個專業的竊賊，準備沿著一條街打劫房屋。每個房子都存放著特定金額的錢。你面臨的唯一約束條件是：相鄰的房子裝著相互聯系的防盜系統，且 當相鄰的兩個房子同一天被打劫時，該系統會自動報警。

給定一個非負整數列表，表示每個房子中存放的錢， 算一算，如果今晚去打劫，在不觸動報警裝置的情況下, 你最多可以得到多少錢 。

您在真實的面試中是否遇到過這個題？
樣例
樣例 1:

輸入: [3, 8, 4]
輸出: 8
解釋: 僅僅打劫第二個房子.
樣例 2:

輸入: [5, 2, 1, 3]
輸出: 8
解釋: 搶第一個和最后一個房子

動態規劃求解
考慮前i項的結果dp[i]時，

dp[i]為到達第i個房間時，得到的最大收益，A為房間錢數組。

當i = 1， 返回dp[0] = A[0]

當i = 2， 返回dp[1] = max(A[0], A[1])

當i = 3， 分為偷3號房屋和不偷3號房屋，

偷的情況下， 2號房間就不能偷了，結果為A[2] + dp[0]

不偷的情況下，結果為dp[1]

所以返回dp[2] = max(dp[0] + A[2], dp[1])

以此類推，dp[i] = max(dp[i-2] + A[i], dp[i-1])

class Solution:"""@param A: An array of non-negative integers@return: The maximum amount of money you can rob tonight"""def houseRobber(self, A):# write your code hereif not A:return 0dp = [0 for _ in A]dp[0] = A[0]for i in range(1, len(A)):if i == 1:dp[i] = max(dp[0], A[i])else:dp[i] = max(dp[i - 2] + A[i], dp[i - 1])return dp[-1] c=Solution() d=c.rob([3,8,4,13]) print(d)

算例5
來源于個人博客
Leetcode 534打劫房屋II python
描述

在上次打劫完一條街道之后，竊賊又發現了一個新的可以打劫的地方，但這次所有的房子圍成了一個圈，這就意味著第一間房子和最后一間房子是挨著的。每個房子都存放著特定金額的錢。你面臨的唯一約束條件是：相鄰的房子裝著相互聯系的防盜系統，且 當相鄰的兩個房子同一天被打劫時，該系統會自動報警。

給定一個非負整數列表，表示每個房子中存放的錢， 算一算，如果今晚去打劫，在不觸動報警裝置的情況下, 你最多可以得到多少錢 。

這題是House Robber的擴展，只不過是由直線變成了圈

您在真實的面試中是否遇到過這個題？
樣例
樣例1

輸入: nums = [3,6,4]
輸出: 6
樣例2

輸入: nums = [2,3,2,3]
輸出: 6

思路：

動態規劃求解
（1）不考慮第一間房子和最后一間房子是挨著的時
考慮前i項的結果dp[i]時，

dp[i]為到達第i個房間時，得到的最大收益，A為房間錢數組。

當i = 1， 返回dp[0] = A[0]

當i = 2， 返回dp[1] = max(A[0], A[1])

當i = 3， 分為偷3號房屋和不偷3號房屋，

偷的情況下， 2號房間就不能偷了，結果為A[2] + dp[0]

不偷的情況下，結果為dp[1]

所以返回dp[2] = max(dp[0] + A[2], dp[1])

以此類推，dp[i] = max(dp[i-2] + A[i], dp[i-1])
（2）考慮第一間房子和最后一間房子是挨著時

區別在于1號房屋和最后一號房屋只能二選一
即把1號房間舍棄，或者最后一號房間舍棄。在這兩種情況下選最優。

class Solution:"""@param nums: An array of non-negative integers.@return: The maximum amount of money you can rob tonight"""def houseRobber(self, nums):# write your code hereif len(nums) == 1:return nums[0]return max(self.houseRobber2(nums[1:]), self.houseRobber2(nums[:-1]))def houseRobber2(self, nums):if len(nums) == 0:return 0dp = [0 for _ in nums]dp[0] = nums[0]for i in range(1, len(nums)):if i == 1:dp[i] = max(nums[0], nums[i])else:dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])return dp[-1]c=Solution() d=c.houseRobber([2,3,2,3]) print(d)

算例6
來源于個人博客
leetcode裝最多水的容器383
描述
給定 n 個非負整數 a1, a2, …, an, 每個數代表了坐標中的一個點 (i, ai)。畫 n 條垂直線，使得 i 垂直線的兩個端點分別為(i, ai)和(i, 0)。找到兩條線，使得其與 x 軸共同構成一個容器，以容納最多水。

容器不可傾斜。

樣例 :

輸入: [1, 3, 2, 2]
輸出: 4
解釋:
選擇 a1, a2, 容量為 1 * 1 = 1
選擇 a1, a3, 容量為 1 * 2 = 2
選擇 a1, a4, 容量為 1 * 3 = 3
選擇 a2, a3, 容量為 2 * 1 = 2
選擇 a2, a4, 容量為 2 * 2 = 4
選擇 a3, a4, 容量為 2 * 1 = 2

#解題思路：
這題等于說求面積最多。假設我們有兩根柱子，命名為left和right。left和right對應橫坐標。它們形成的面積應為
ans=(right-left)*min(height[left],height[right]）.
求解時我們應該不斷更新這個數據:
ans=max(ans,(right-left)*min(height[left],height[right]))。
開始我們的迭代。
（1）面積ans=max(ans,(right-left)*min(height[left],height[right])).
(2)left從左往右走，rgiht同時 從右往左走.
(3)比較left與right的高度,高的先不動，移動矮的。
迭代結束條件為left和right指向同一點。

class Solution(object):def maxArea(self,height):ans=left=0right=len(height)-1while left<right:ans=max(ans,(right-left)*min(height[left],height[right]))if height[left]<=height[right]:left+=1else:right-=1return ansc=Solution() a=[1, 3, 2] d=c.maxArea(a) print(d)

結果2

算例7
來源于個人博客
leetcode111 爬樓梯 python實現
動態規劃類題目
描述

假設你正在爬樓梯，需要n步你才能到達頂部。但每次你只能爬一步或者兩步，你能有多少種不同的方法爬到樓頂部？

您在真實的面試中是否遇到過這個題？
樣例
Example 1:
Input: n = 3
Output: 3

Explanation:

1, 1, 1

1, 2

2, 1
total 3.
1
2
3
4
5
Example 2:
Input: n = 1
Output: 1

Explanation:
only 1 way.
1
2
思路：上第I級臺階的方法總共有兩大種，第一種是從第（i-1）級臺階上跨一級，第二種則是從第（I-2）級臺階上跨兩級，除此并無他法，由于這個上樓方法從（i-1）和（i-2）級各只有一種方法，那么上第i級臺階的總的方法和數就是上前兩級臺階的方法總和數

思路遞歸代碼

class Solution:"""@param n: An integer@return: An integer"""def climbStairs(self, n):# write your code hereif n==0:return 0if n==1:return 1pre,ppre=1,1# pre,ppre前時刻，前2時刻for i in range(2,n+1):tmp = pre#tmp 用于pre ,與ppre 完成數值改變pre = pre + ppre#當前等于前面兩步相加ppre = tmp#前一時刻變成前前時刻return pre

來源 @Author: yudengwu

總結

以上是生活随笔為你收集整理的动态规划原理介绍（附7个算例，有代码讲解）的全部內容，希望文章能夠幫你解決所遇到的問題。

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