python 動態規劃

性質

1. 最優子結構性質，如果問題的最優解所包含的子問題的解也是最優的，我們就稱該問題具有最優子結構性質（即滿足最優化原理），最優子結構性質為動態規劃演算法解決問題提供了重要線索，
2. 子問題重疊性質，子問題重疊性質是指在用遞回演算法自頂向下對問題進行求解時，每次產生的子問題并不總是新問題，有些子問題會被重復計算多次，動態規劃演算法正是利用了這種子問題的重疊性質，對每一個子問題只計算一次，然后將其計算結果保存在一個表格中，當再次需要計算已經計算過的子問題時，只是在表格中簡單地查看一下結果，從而獲得較高的效率，
3. 無后效性：即某階段狀態一旦確定，就不受這個狀態以后決策的影響，也就是說，某狀態以后的程序不會影響以前的狀態，只與當前狀態有關，

將待求解的問題分解為若干個子問題（階段），按順序求解子階段，前一子問題的解，為后一子問題的求解提供了有用的資訊，在求解任一子問題時，列出各種可能的區域解，通過決策保留那些有可能達到最優的區域解，丟棄其他區域解，依次解決各子問題，最后一個子問題就是初始問題的解，

動態規劃中的子問題往往不是相互獨立的（即子問題重疊），在求解的程序中，許多子問題的解被反復地使用，為了避免重復計算，動態規劃演算法采用了填表來保存子問題解的方法，

適用問題

適合用動態規劃來解決的問題，都具有下面三個特點：最優化原理、無后效性、有重疊子問題，

（1）最優化原理：如果問題的最優解所包含的子問題的解也是最優的，就稱該問題具有最優子結構，即滿足最優化原理，

（2）無后效性：即某階段狀態一旦確定，就不受這個狀態以后決策的影響，也就是說，某狀態以后的程序不會影響以前的狀態，只與當前狀態有關，

（3）有重疊子問題：即子問題之間是不獨立的，一個子問題在下一階段決策中可能被多次使用到，（該性質并不是動態規劃適用的必要條件，但是如果沒有這條性質，動態規劃演算法同其他演算法相比就不具備優勢，
演算法實作
動態規劃三要素：

（1）問題的階段

（2）每個階段的狀態

（3）相鄰兩個階段之間的遞推關系

整個求解程序可以用一張最優決策表來描述，最優決策表是一張二維表（行：決策階段，列：問題的狀態）表格需要填寫的資料一般對應此問題的在某個階段某個狀態下的最優值（如最短路徑，最長公共子序列，最大價值等），填表的程序就是根據遞推關系，最后根據整個表格的資料通過簡單的取舍或者運算求得問題的最優解，

例如：f(n,m)=max{f(n-1,m), f(n-1,m-w[n])+P(n,m)}

1. 背包問題

假設我們有n種型別的物品，分別編號為1, 2...n，其中編號為i的物品價值為vi，它的重量為wi，為了簡化問題，假定價值和重量都是整數值，現在，假設我們有一個背包，它能夠承載的重量是Cap，現在，我們希望往包里裝這些物品，使得包里裝的物品價值最大化，那么我們該如何來選擇裝的東西呢？注意：每種物品只有一件，可以選擇放或者不放，初始化資料為：n=5，w={2,2,6,5,4}，v={6,3,5,4,6}，Cap=10

情況1: 如果第i件物品不能放（即這個物品的重量直接大于了當前限重v），則問題轉化為“前i-1件物品放入容量為v的背包中”，即f[i-1][v]；

情況2: 如果放第i件物品是可以放也可以不放，則問題轉化為：

? 1）、如果選擇不放第i件物品，則問題轉化為“前i-1件物品放入容量為v的背包中”，即變大時f[i-1][v]；

? 2）、如果選擇放第i件物品，則問題轉化為“前i-1件物品放入剩下的容量為v-w[i]的背包中”，此時能獲得的最大價值就是f [i-1][v-w[i]]再加上通過放入第i件物品獲得的價值v[i]，

最優子結構描述如下：當子問題f[i][v]是最優時，其子問題f[i-1][v]和f[i-1][v-w[i]]（中的較大者）顯然同樣也必須是最優的值，不然在情況1或者情況2下總會矛盾，

B) 遞回定義最優解的值

根據上面的分析，顯然子問題

f[i][v]=f[i-1][v]，這時是情況1

f[i][v]=max{f[i-1][v], f[i-1][v-w[i]]+v[i] }，這時是情況2，

import numpy as np

def solve(num,Weight,wlist,pricelist):
    a = np.array([[0]*(Weight+1)]*(num+1))
    #用numpy新建一個陣列出來，每一個值都表示當前情況下的最油重量，
    # 坐標即為放第i個物品，以及當前容量
    for i in range(1,num+1):
        for j in range(1,Weight+1):
            if wlist[i-1] > j:
                a[i,j] = a[i-1,j]#如果當前要放的超過了當前容量，就不放了
            else:
                a[i,j] = max(a[i-1,j],pricelist[i-1]+a[i-1,j-wlist[i-1]])
                # 如果不放->a[i-1,j],
                # 如果放-> 之前考慮放之前存好的最大重量相比
    print(a)

weights = [1,2,5,6,7,9]
price = [1,6,18,22,28,36]
solve(len(weights),13,weights,price)
[[ 0  0  0  0  0  0  0  0  0  0  0  0  0  0]
 [ 0  1  1  1  1  1  1  1  1  1  1  1  1  1]
 [ 0  1  6  7  7  7  7  7  7  7  7  7  7  7]
 [ 0  1  6  7  7 18 19 24 25 25 25 25 25 25]
 [ 0  1  6  7  7 18 22 24 28 29 29 40 41 46]
 [ 0  1  6  7  7 18 22 28 29 34 35 40 46 50]
 [ 0  1  6  7  7 18 22 28 29 36 37 42 46 50]]

2. 最長公共子序列

給定兩個字串str1和str2，回傳兩個字串的最長公共子序列，例如：str1="1A2C3D4B56",str2="B1D23CA45B6A","123456"和"12C4B6"都是最長公共子序列，回傳哪一個都行，

分析：本題是非常經典的動態規劃問題，假設str1的長度為M，str2的長度為N，則生成M*N的二維陣列dp，dp[i][j]的含義是str1[0..i]與str2[0..j]的最長公共子序列的長度，

dp值的求法如下：

dp[i][j]的值必然和dp[i-1][j],dp[i][j-1],dp[i-1][j-1]相關，結合下面的代碼來看，我們實際上是從第1行和第1列開始計算的，而把第0行和第0列都初始化為0，這是為了后面的取最大值在代碼實作上的方便，dp[i][j]取三者之間的最大值，

def find_lcsubstr(s1, s2):
	# 下面4行不要直接寫在回圈中，減少計算
	s1_len = len(s1) + 1 					#為方便后續計算，多了1行1列
	s2_len = len(s2) + 1
	s3_len = len(s1)
	s4_len = len(s2)
	m = [[0 for j in range(s2_len)] for i in range(s1_len)] #生成0矩陣
	maxNum = 0   							#初始最長匹配長度
	p = 0  									#匹配的起始位置
	for i in range(s3_len):
		for j in range(s4_len):
			if s1[i] == s2[j]:				  #相同則累加
				m[i + 1][j + 1] = m[i][j] + 1 #給相同字符賦值，值為左上角值加1
				if m[i + 1][j + 1] > maxNum:
					maxNum = m[i + 1][j + 1]  #獲取最大匹配長度
					p = i + 1 				  #記錄最大匹配長度的終止位置
	print(m)
	return s1[p - maxNum : p], maxNum   	  #回傳最長子串及其長度

3. 最長子回文串

Example 1:

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

Example 2:

Input: s = "cbbd"
Output: "bb"

思路與方法

如果一個子串是回文串，并且長度大于2，那么將他首位字母去掉之后依然是一個回文串，例如ababa,去掉之后bab是回文的，根據這樣的思路，我們就可以用動態規劃的方法解決本題，我們用 P[i,j]表示字串P的子串

這里的其他情況包含兩種：

那么我們就可以寫出動態規劃的狀態轉移方程：

意思就是只有當棄掉兩邊S_i和S_j是回文串，并且首尾字母依然相等，則更大子串也是回文串，

注意：在狀態轉移方程中，我們是從長度較短的字串向長度較長的字串進行轉移的，因此一定要注意動態規劃的回圈順序，

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        if n < 2:
            return s

        max_len = 1
        begin = 0
        # dp[i][j] 表示 s[i..j] 是否是回文串
        dp = [[False] * n for _ in range(n)]
        for i in range(n):
            dp[i][i] = True

        # 遞推開始
        # 先列舉子串長度
        for L in range(2, n + 1):
            # 列舉左邊界，左邊界的上限設定可以寬松一些
            for i in range(n):
                # 由 L 和 i 可以確定右邊界，即 j - i + 1 = L 得
                j = L + i - 1
                # 如果右邊界越界，就可以退出當前回圈
                if j >= n:
                    break

                if s[i] != s[j]:
                    dp[i][j] = False
                else:
                    if j - i < 3:
                        dp[i][j] = True
                    else:
                        dp[i][j] = dp[i + 1][j - 1]

                # 只要 dp[i][L] == true 成立，就表示子串 s[i..L] 是回文，此時記錄回文長度和起始位置
                if dp[i][j] and j - i + 1 > max_len:
                    max_len = j - i + 1
                    begin = i
        return s[begin:begin + max_len]



s = Solution()
ans = s.longestPalindrome("abcdeed")
print(ans)

本文來自博客園，作者：ivanlee717，轉載請注明原文鏈接：https://www.cnblogs.com/ivanlee717/p/17268425.html

標籤：Python

上一篇：python基礎篇：python中有哪些資料型別，你知道嗎？

下一篇：【manim影片教程】-- 基本圖形