我剛剛在 leetcode.com 上使用遞歸解決了這個(gè)問(wèn)題（10.正則表達(dá)式匹配）。我能夠理解遞歸解決方案。但是，當(dāng)我看到這段代碼的優(yōu)化版本時(shí)，建議我應(yīng)該使用Dynamic Programming。我不明白為什么我們需要?jiǎng)討B(tài)編程？我沒(méi)有看到這個(gè)問(wèn)題有重疊的子問(wèn)題。我們?yōu)槭裁匆褂糜洃浕蛑票?？我無(wú)法想象重疊的子問(wèn)題。這是我到目前為止到達(dá)的地方。這是我的解決方案：public static boolean isMatch(String text, String pattern) {if (pattern.isEmpty())    return text.isEmpty();boolean first_match = (!text.isEmpty() && (pattern.charAt(0) == text.charAt(0) || pattern.charAt(0) == '.'));if (pattern.length() >= 2 && pattern.charAt(1) == '*') {    return isMatch(text, pattern.substring(2))|| first_match && isMatch(text.substring(1), pattern);} else {    return first_match && isMatch(text.substring(1), pattern.substring(1));}我對(duì)遞歸解決方案的理解是，我可以看到模式中的下一個(gè)字符是否是 *，那么可能有兩種情況：我們跳過(guò)當(dāng)前字符和下一個(gè)字符（*）并從索引 2 中獲取模式的子字符串，并將模式的剩余子字符串與當(dāng)前文本進(jìn)行匹配。這說(shuō)明 * 前的字符出現(xiàn)“0”次。模式中的 * 將不斷吸收文本中的匹配字符。只要我們繼續(xù)獲得相同的角色，他們就會(huì)繼續(xù)匹配明星，我們就會(huì)繼續(xù)前進(jìn)。另一種情況是，如果下一個(gè)字符不是“*”，那么我們檢查當(dāng)前字符是否匹配，如果是，則檢查兩者的剩余子字符串。我嘗試使用以下方法進(jìn)行干運(yùn)行：輸入：s = "mississippi" p = "mis*is*p*." 輸出：假我可以想象第一個(gè) m 和 m 匹配，i 和 i 匹配（到目前為止是線(xiàn)性遞歸）。現(xiàn)在開(kāi)始復(fù)雜的部分，因?yàn)?s 和 s 匹配但 s 的下一個(gè)字符是星號(hào)。如果我調(diào)用，匹配 '0' 出現(xiàn)作為場(chǎng)景 1 并吸收 * 作為場(chǎng)景 2 中的匹配字符，那么遞歸調(diào)用將如下所示：場(chǎng)景 1： text 是 ssissippi ，剩余模式是p。s 和 i 字符不匹配場(chǎng)景 2：剩余文本是 sissippi，模式是 s是p*。場(chǎng)景 1：文本是 sissippi，剩余模式是p。s 和 i 字符不匹配場(chǎng)景 2：剩余文本是 issippi，模式是 s是p*。場(chǎng)景 1： text 是 issippi ，剩余模式是p。字符匹配所以下一個(gè)遞歸調(diào)用文本：ssippi 和模式為：s p。場(chǎng)景 1：文本為 ssippi，剩余模式為 p*。場(chǎng)景 1：文本為 ssippi，剩余模式為 .字符匹配所以下一個(gè)遞歸調(diào)用文本：sippi 和模式為：場(chǎng)景 2：剩余文本為 sippi，模式為 p*。場(chǎng)景 2：剩余文本為 sippi ，模式為 s p。場(chǎng)景 1：文本是 sippi，剩余模式是 p*。場(chǎng)景 1：文本是 sippi，剩余模式是 .字符匹配，因此下一個(gè)遞歸調(diào)用與文本：ippi 和模式為：場(chǎng)景 2：剩余文本為 ippi，模式為 p*。場(chǎng)景2：剩余文本為 ippi ，模式為 s p。場(chǎng)景 1：文本為 ippi，剩余模式為 p*。場(chǎng)景1：文本為ippi，剩余模式為.字符匹配所以下一個(gè)遞歸調(diào)用文本：ppi 和模式為：場(chǎng)景 2：剩余文本為 ppi，模式為 p*。場(chǎng)景2：剩余文本為 ppi ，模式為 s p。場(chǎng)景 2：剩余文本是 ssippi，模式是 s是p*。最后返回False。在此解決方案中，我無(wú)法確定是否存在任何重疊的子問(wèn)題或任何我們可以重用的解決方案？我什至嘗試在youtube上查找。這家伙沒(méi)有告訴我們是如何得到這個(gè)解決方案的，他只是簡(jiǎn)單地試運(yùn)行這個(gè)解決方案，因?yàn)樗肋@是一個(gè) DP 問(wèn)題。我們?nèi)绾未_定這是否是 DP 問(wèn)題？為這個(gè)問(wèn)題達(dá)成 DP 解決方案背后的直覺(jué)是什么？我在互聯(lián)網(wǎng)上查了很多資料，但我仍然無(wú)法弄清楚重疊的子問(wèn)題在哪里，以及我們?nèi)绾蔚贸鼋Y(jié)論是否是 DP 問(wèn)題。我也嘗試為這個(gè)樹(shù)制作一個(gè)遞歸樹(shù)，但仍然無(wú)法弄清楚我們可以在哪里重新使用以前計(jì)算的解決方案。任何人都可以幫助我想象重疊的子問(wèn)題，并幫助我得出結(jié)論，您如何確定它是否是 DP 問(wèn)題并找到自下而上的解決方案？