响应式网站开发教程pdf,哈尔滨巨耀网站建设,东莞城乡建设,微信的微网站模板下载不了392.判断子序列
https://programmercarl.com/0392.%E5%88%A4%E6%96%AD%E5%AD%90%E5%BA%8F%E5%88%97.html
考点 子序列问题 我的思路 dp[i][j]的含义是#xff0c;两个序列分别取到下标为i和j的时候#xff0c;他们是否满足前者是后者的子序列#xff0c;满足为True#x…392.判断子序列
https://programmercarl.com/0392.%E5%88%A4%E6%96%AD%E5%AD%90%E5%BA%8F%E5%88%97.html
考点 子序列问题 我的思路 dp[i][j]的含义是两个序列分别取到下标为i和j的时候他们是否满足前者是后者的子序列满足为True否则为False递推公式分为后者序列取到第j - 1个元素时就已经满足前者序列为其子序列的情况、dp[i - 1][j - 1]满足子序列要求且前者序列的第i个元素和后者序列的第j个元素恰好相等的情况、以及dp[i][j]不满足为子序列的情况初始化建议画出二维矩阵并举一个例子来分析仅额外初始化后者序列对应的第一条边即可将所有满足子序列要求的位置设置为True其与都为False 视频讲解关键点总结 和我的思路不太一样 我的思路的问题 无 代码书写问题 无 可执行代码
class Solution:def isSubsequence(self, s: str, t: str) - bool:if s :return Trueelif t :return Falsedp [[False] * len(t) for _ in range(len(s))]for i in range(len(t)):if t[i] s[0]:for j in range(i, len(t)):dp[0][j] Truebreakfor i in range(1, len(s)):for j in range(1, len(t)):if dp[i][j - 1]:dp[i][j] Trueelif s[i] t[j] and dp[i - 1][j - 1]:dp[i][j] Truereturn dp[-1][-1]*115.不同的子序列
https://programmercarl.com/0115.%E4%B8%8D%E5%90%8C%E7%9A%84%E5%AD%90%E5%BA%8F%E5%88%97.html
考点 子序列问题 我的思路 无思路 视频讲解关键点总结 明确本题的目标我们是要在后者元素中删除元素获得子序列来让该子序列与前者序列相同dp[i][j]的含义是两个序列分别取到下标为i和j的时候后者序列能组合出多少种和前者序列相同的子序列递推公式如果当前下标的元素相同则可以同时取当前下标元素此时dp[i][j] dp[i - 1][j - 1]或者不取后者序列的当前元素此时dp[i][j] dp[i][j - 1]如果当前下标的元素不相同则只有dp[i][j] dp[i][j - 1]初始化建议画出二维矩阵并举一个例子来分析仅额外初始化后者序列对应的第一条边即可 我的思路的问题 无思路 代码书写问题 无 可执行代码
class Solution:def numDistinct(self, s: str, t: str) - int:dp [[0] * len(s) for _ in range(len(t))]if s[0] t[0]:dp[0][0] 1for i in range(1, len(s)):if t[0] s[i]:dp[0][i] dp[0][i - 1] 1else:dp[0][i] dp[0][i - 1]for i in range(1, len(t)):for j in range(1, len(s)):if s[j] t[i]:dp[i][j] dp[i - 1][j - 1] dp[i][j - 1]else:dp[i][j] dp[i][j - 1]return dp[-1][-1]
