我真的被困在一個問題上，我得到了一個字串輸入 S、另一個表示整個子字串的字串輸入 U 和一個非負整數 m。方法是lcs(S, U, m)。
例如：設 S="aabacaab"、U="aab" 和 m=2。然后我們有以下子串組合：
[a][ab]acaab
[a]abaca[ab]
a[a]baca[ab]
aab[a]ca[ab]
aabac[a][ab]
[aa][b]acaab
[aa]bacaa[b]
aabac[aa][b]
因此lcs(S, U, m)回傳，8因為我們有 8 種不同的 U 子串組合，并且限制m了子串的數量。
我最初的想法是將 的第一個字符S與的第一個字符進行比較，U并通過縮短S和向下遞回U。但是，由于m，我無法確定m應該如何減少作為縮短的S并且U沒有任何對先前狀態的參考。
uj5u.com熱心網友回復：
在處理字串上的動態規劃時，“我的子問題應該是什么”的答案通常是前綴、后綴或子字串。
從您最后的注釋中，您已經正確地確定我們可以通過解決后綴問題來解決原始問題。我們也知道我們的子問題必須知道我們還剩下多少塊可以使用。此時，我們可以猜測子問題是什么，并嘗試定義一個公式。
我們可以讓f(i,j,k)有辦法匹配最后數量j的字母U用最后一個i字母S為準確k子。什么是邊緣情況？如果j和k都為0，我們無事可做；有 1 種方法什么都不做。如果i<j我們不能匹配j字母，如果j<k我們不能將j字母分成足夠多的部分。
最后，您必須定義主遞回。首先，我們可以跳過 的這個字母S，它f(i-1,j,k)作為被加數給出。現在，讓Match-Length(i,j)成為S[-i:]比賽開始時的連續位置數U[-j:]。我們需要添加所有可能的匹配項：對于每個長度l, 1 <= l <= Match-Length(i,j)，我們必須添加f(i-l, j-l, k-1)。這涵蓋了所有情況。
編輯：用戶 qouify 發布了一個更好的解決方案。這個 DP 公式的直接翻譯及時運行O(|S| |U|^2 m)，而他們的運行在O(|S| |U| m). 可以修改我的公式以匹配該運行時，但您需要計算前綴總和，以便在預處理和記憶后f(i-l, j-l, k-1)可以及時找到每個總和O(1)。
uj5u.com熱心網友回復：
縮短m，你將不得不尋找在當前的字母S
和U。如果兩個字母相同，您有兩種情況會考慮兩種（非排他性）情況：
您當前正在匹配的子字串
S（這意味著，使用您的符號，您已經打開了一個字串，例如[aa...），在這種情況下，您可以繼續該匹配您仍然有嚴格正數的子字串要匹配，在這種情況下，您可以開始新的匹配（無論您當前是否匹配字串）
為此，您將需要一個額外的遞回引數來指定您當前是否匹配子字串。
表明您已找到與您的問題匹配的基本情況是當您到達 的末尾U并且m等于 時0。
這是實作此解決方案的代碼（請注意，該函式處理字母串列而不是字串）：
#!/usr/bin/env python3
import functools
def lcs(s, u, m) -> int:
# recursive function
# i: index in list s
# j: index in list j
# m: number of sub-strings to find
# match: are we currently matching a sub-string or not?
@functools.lru_cache(maxsize=10000) # cache the result of our function
def loop(i, j, m, match) -> int:
# base cases
if j >= len(u): # end of u reached => no more letter to look for
if m == 0: # check if have found our m sub-strings
return 1
return 0
if i >= len(s): # end of s reached and still letter to look for
return 0
result = loop(i 1, j, m, False) # skip the current letter
# letter in s and u are the same (we will move both i and j)
if s[i] == u[j]:
if match: # we are currently matching a sub-string => continue
result = loop(i 1, j 1, m, True)
if m > 0: # we can start a new sub-string
result = loop(i 1, j 1, m - 1, True)
return result
return loop(0, 0, m, False)
print(lcs(list("aabacaab"), list("aab"), 2))
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/328813.html