我剛剛開始學習動態編程，并且能夠做一些基本的問題，比如斐波那契、背包和其他一些問題。遇到下面的問題，我卡住了，不知道如何繼續。讓我困惑的是在這種情況下的基本情況是什么，以及重疊的問題。不知道這一點會阻止我發展關系。在這個例子中，它們不像在我迄今為止解決的以前的例子中那樣明顯。
假設我們給定了一些字串 origString、一個字串 toMatch 和一些大于或等于 0 的數字 maxNum。我們如何計算有多少種方法可以采用字串 origString 的非空和非重疊子串的 maxNum 個數來組成字串匹配？
例子：
如果 origString = "ppkpke", and toMatch = "ppke"
maxNum = 1: countWays("ppkpke", "ppke", 1) 將給出 0，因為 toMatch 不是 origString 的子字串。
maxNum = 2: countWays("ppkpke", "ppke", 2) 將給出 4，因為由“ppkpke”組成的 2 個子串的 4 種不同組合可以生成“ppke”。這些字串是 "ppk" & "e", "pp" & "ke" , "p" & "pke" (不包括 "p") 和 "p" & "pke" (不包括 "k")
uj5u.com熱心網友回復：
這是一個遞回解決方案。
比較sourceand的第一個字符target，如果它們相等，選擇接受它（在兩個字串中前進 1 個字符）或不接受它（前進 1 個字符 insource但不是 in target）。k每次創建新的子串時，的值都會遞減；continued如果我們正在構建子字串，則有一個額外的變數為 True，否則為 False。
def countWays(source, target, k, continued=False):
if len(target) == 0:
return (k == 0)
elif (k == 0 and not continued) or len(source) == 0:
return 0
elif source[0] == target[0]:
if continued:
return countWays(source[1:], target[1:], k, True) countWays(source[1:], target[1:], k-1, True) countWays(source[1:], target, k, False)
else:
return countWays(source[1:], target[1:], k-1, True) countWays(source[1:], target, k, False)
else:
return countWays(source[1:], target, k, False)
print(countWays('ppkpke', 'ppke', 1))
# 0
print(countWays('ppkpke', 'ppke', 2))
# 4
print(countWays('ppkpke', 'ppke', 3))
# 8
print(countWays('ppkpke', 'ppke', 4))
# 4
print(countWays('ppkpke', 'ppke', 5))
# 0
uj5u.com熱心網友回復：
作為最初的警告，我要說的是，盡管我的解決方案恰好與小測驗集的預期輸出相匹配，但很可能是錯誤的。您可以根據您可能擁有的其他示例進行仔細檢查等。
該演算法遍歷較長的字串并嘗試將較短的字串散布在其上。演算法的增量狀態由 3 個元素的元組組成：
- 長字串坐標
i(origString[i] == toMatch[j]) - 短字串坐標
j(origString[i] == toMatch[j]) - 我們進入那個狀態的方法數^^^
然后我們只是一遍又一遍地沿著字串走，使用存盤的、先前發現的狀態，并總結每個狀態實作的方式總數——以典型的動態編程方式。
對于算作解決方案的狀態，j必須位于短字串的末尾，并且動態演算法的迭代次數必須等于我們當時想要的子字串數（因為每次迭代添加一個子字串）。
從分配中我并不完全清楚是否maxNum真的意味著像“ exactNum”這樣的東西，即恰好那么多子串，或者我們是否應該對所有較小或相等數量的子串求和。因此該函式回傳一個像{#substrings :#decompositions}這樣的字典，以便可以根據需要調整輸出。
#!/usr/bin/env python
def countWays(origString, toMatch, maxNum):
origLen = len(origString)
matchLen = len(toMatch)
state = {}
for i in range(origLen):
for j in range(matchLen):
o = i j
if origString[o] != toMatch[j]:
break
state[(o, j)] = 1
sums = {}
for n in range(1, maxNum):
if not state:
break
nextState = {}
for istart, jstart in state:
prev = state[(istart, jstart)]
for i in range(istart 1, origLen):
for j in range(jstart 1, matchLen):
o = i j - jstart - 1
if origString[o] != toMatch[j]:
break
nextState[(o, j)] = prev nextState.get((o, j), 0)
sums[n] = sum(state[(i, j)] for i, j in state if j == matchLen - 1)
state = nextState
sums[maxNum] = sum(state[(i, j)] for i, j in state if j == matchLen - 1)
return sums
result = countWays(origString='ppkpke', toMatch='ppke', maxNum=5)
print('for an exact number of substrings:', result)
print(' for up to a number of substrings:', {
n: s for n, s in ((m, sum(result[k] for k in range(1, m 1)))
for m in range(1, 1 max(result.keys())))})
這個^^^ 代碼是一個快速而丑陋的黑客，僅此而已。有很大的改進空間，包括（但不限于）生成器函式（yield）的使用，@memoize等的使用。以下是一些輸出：
for an exact number of substrings: {1: 0, 2: 4, 3: 8, 4: 4, 5: 0}
for up to a number of substrings: {1: 0, 2: 4, 3: 12, 4: 16, 5: 16}
It would be an interesting (and nicely challenging) exercise to store a bit more of the dynamic state (e.g. to keep it for each n) and then reconstruct and pretty-print (efficiently) the exact string (de)compositions that were counted.
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/313551.html
上一篇：在樹結構中尋找最高父級