392的Python解决方案.是子序列

Question

我已经解决了LeetCode上的解决方案392，其中列出的主题之一是动态编程。在网上查看我的代码和其他解决方案时，我想知道解决方案的哪一部分属于动态编程。如果有人能启发我，帮助我更好地理解这一点，我将不胜感激。

解决方案的解释在LeetCode上对我来说是付费的，因为我没有溢价，所以我正在努力开源这种理解。

解决方案：

def isSubsequence(self, s: str, t: str) -> bool:
if len(s) == 0:
return True
if len(t) == 0:
return False
temp = ''
count = 0
for i in t:
if count < len(s) and i == s[count]:
temp += i
count += 1
if temp == s:
return True
else:
return False

链接：https://leetcode.com/problems/is-subsequence/

Answer 1

正如所评论的，发布的解决方案是您的方法是一个双指针算法的例子

为了创建一个动态编程问题的解决方案，我们可以分为三个步骤

1. 找到第一个解决方案(基本情况(
2. 分析解决方案
3. 优化解决方案

步骤1：第一个解决方案

这里有一个递归的自上而下的解决方案来解决这个问题。

• 递归解决方案分解为子问题
• 如果s为空字符串问题已解决(返回True(
• 如果t为空，则问题已解决(返回False(
• 如果第一个字母匹配=>返回s&t
• 否则，在t的第一个字母后匹配s

代码

def isSubsequence(s, t):
# Base Cases
if not s:
return True  # s is empty
elif not t:
return False  # t is empty
# Recursive case
# if first letters match, solve after first letters of s & t
# else find s after first letter of t
return isSubsequence(s[1:], t[1:]) if s[0] == t[0] else isSubsequence(s, t[1:])

第2步：分析

• 递归提供了一个简单的实现
• 通常情况下，回避是低效的，因为它会一次又一次地重复解决相同的子问题
• 然而，在这种情况下，子问题不会重复求解

例如；ab"；是"的子序列；xaxb"；我们有以下调用树：

isSubsequence("ab", 'xaxb')         # to check "ab" against "xaxb"
isSubsequence("ab", "axb")          # we check these sequence of subproblems
isSubsequence("b", "xb")            # but each is only checked once
isSubsequence("b", "b")
isSubsequenc("", "")
return True

步骤3：优化

在这种情况下，解决方案已经优化。对于像这样的其他递归解决方案，我们将使用记忆来优化

• 避免重复求解亚解
• 可以使用缓存Python 3.9+或lru_cache(Python 3.9之前的版本(进行内存化

记忆代码(注意：在这种情况下没有必要(

from functools import lru_cache

@lru_cache(maxsize=None)
def isSubsequence(s, t):
# Base Cases
if not s:
return True  # s is empty
elif not t:
return False  # t is empty
# Recursive case
# if first letters match, solve after first letters of s & t
# else find s after first letter of t
return isSubsequence(s[1:], t[1:]) if s[0] == t[0] else isSubsequence(s, t[1:])