Becomin' Charles

算法 | LNMP | Flutter | Mac

Becomin' Charles

这道题的意思比较简单,我就不在这里抄题目了,可以去这里查看。简单说,就是在给定字符串里,找到一个连续的子串,这个子串里所有的字符都不同,求这个其中长度最大的子串的长度。

做这种题目,首先要关注一下题目的规模,底下提示,这个给定的字符串,长度范围在 0 到 50000。一般来说,如果是求一个子串的题目,首先想的是,怎么在一个字符串里唯一确定一个子串呢?那就是确定这个子串的开头和结尾位置。

如果我们想穷举所有的子串的话,开头位置取值有 n 个可能,结尾位置取值也有 n 个可能,所以,整个搜索空间是 25 亿!所以,我们必然不能穷举。

那么怎么去设计算法呢?我们可以试试数学归纳法。

假设我们已经知道了如何求解以第 n 个字符结尾的最长子串,那么对于第 n + 1 个字符来说,怎么求解最长子串呢?如果我们知道以第 n 个字符结尾的子串,那么对于第 n + 1 个字符,有两种情况,第一,第 n + 1 个字符在最长子串中没出现过,那么,以第 n + 1 个字符为结尾的最长子串就是 substr + s[n + 1],第二种情况,第 n + 1 个字符已经出现了,那么我们把它的位置算出来 pos,然后把 pos 及以前的字符删掉,然后把第 n + 1 个字符接在后面,就形成了以 第 n+1 个字符结尾的最长子串。

怎么求整体的最长子串呢?就是遍历每个结尾位置即可。最大的那个长度就是答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
@cache
def longestSubstr(idx: int) -> (str, int):
if idx == 0:
return s[idx], 1
sub, l = longestSubstr(idx - 1)
if s[idx] not in sub:
return sub + s[idx], l + 1
else:
pos = sub.index(s[idx])
return sub[pos + 1:] + s[idx], l - pos
ans = 0
for i in range(len(s)):
_, l = longestSubstr(i)
ans = max(ans, l)
return an

利用上面的原理,我设计了一个递归算法,计算以 idx 结尾的最长子串,就是计算 idx - 1 为结尾的子串,并进行两种情况而处理。

然后,我们很容易意识到,例如,计算以 下标5 结尾的子串时,要先计算 下标4 结尾的子串。假如我们用一个缓存,记录所有的中间结果,那么遍历的时候,就可以节省大量而时间。上面我用了 Python 的修饰符 @cache。最平凡的情况就是 idx = 0 的时候,显然此时最长子串就是 1,因为里面只有一个字符。

这个算法写出来后,我们就发现,动态规划的写法其实已经呼之欲出了。状态转移方程,就是 n 与 n - 1 之间的关系,前面也都说了:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
curStr = ""
res = 0
n = len(s)

for i in range(n):
if s[i] in curStr:
pos = curStr.index(s[i])
curStr = curStr[pos + 1:] + s[i]
else:
curStr += s[i]
res = max(res, len(curStr))
return res

这个算法里,curStr 就是最长的无重复字符的子串。相当于我们一旦发现了重复字符,我们就把子串从重复字符开始的前缀给截掉。

这个算法的时间复杂度,大框架上是 O(n) 的,因为我们只遍历了一次字符串,这里消耗时间的还有一个地方,就是我们用了字符串的 index 操作,这个操作本质上也应该是 O(n) 的复杂度,不过我们可以用 一个 hash 来优化这个查询的复杂度到 O(1)。

从这个算法里,我们看到,遍历字符串结尾位置的时候,只要遍历一遍,那么子串开头的位置变化有什么特点呢?当我们没有截断子串的时候,开头的位置是不变的,当我们截断了的时候,开头位置往右移动(增大)。不难发现,子串的开始位置和结束位置,在遍历过程中,变化都是单调的。

这个特点就提醒我们,我们可以用一个开始位置或结束位置一直往右移动的滑动窗口来实现算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
freq = set()
ans = 0
n = len(s)

right = -1

for i in range(n):
if i:
freq.remove(s[i - 1])

while right + 1 < n and s[right + 1] not in freq:
freq.add(s[right + 1])
right += 1

ans = max(ans, right - i + 1)
return ans

在这里,我们用一个数据结构集合(set),来记录字符是否出现。然后我们遍历子串的起始位置,然后向右扩展结束位置,如果发现重复字符,就把起始位置右移,没重复,就把结束位置右移。也是 O(n) 的复杂度。

当我们遍历一棵二叉树的时候,根据遍历根节点的顺序的不同,可以有三种方法,前序遍历(Preorder),中序遍历(Inorder),后序遍历(Postorder)。分别对应着先访问根节点,在先左子树,然后访问根节点,接着右子树,或者最后访问根节点。这是很基本的数据结构知识点。今天的题目就是,给定一个二叉树的前序遍历和中序遍历结果,根据这个还原出二叉树。

其实前序遍历加中序遍历结果,就会唯一确定一棵二叉树。现在无非怎么操作的问题。我们可以从一个实例来分析这个:

1
2
preorder = [1, 2, 3, 4, 5, 6, 7, 8, 9]
inorder = [3, 2, 4, 1, 6, 5, 8, 7, 9]

前序遍历的第一个节点是 1,则,在中序遍历中 3,2,4,[1],6,5,8,7,9,就把序列分成了两份,前半段是左子树,后半段就是右子树。前序遍历的第二个节点是 2,则中序中的前半段 3,[2],4,通过 2 把它又分成了两段,3,就是左子树,4,就是右子树。正好对应着前序遍历的第三个节点和第四个节点……

从这个顺序里,我们可以发现,前序遍历序列,我们只要按顺序逐个处理,而中序遍历的,我们不断分割左右两半,然后就是递归地处理这个过程。基于这个原理,我们可以用 Python 很简洁地写出这个方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
n = len(preorder)
pre = iter(preorder)

def rec(left: int, right: int) -> TreeNode:
if left >= right:
return None
r = next(pre)
m = inorder.index(r, left, right)
ltree = rec(left, m)
rtree = rec(m + 1, right)
return TreeNode(r, ltree, rtree)

return rec(0, n)

我们声明一个函数 rec,代表 reconstruction(重建),用下标 left 和 right 来标记中序遍历序列的下标。因为前序遍历序列的分析,就是按顺序,所以我们生成一个迭代器来操作它,而下标 left 和 right,作用就是探测已到达叶子节点的标记。因为 index 这个方法的搜索范围是左闭右开区间的,所以我们对 left 和 right 的取值控制也是左闭右开的,这点需要注意。(为什么递归终止条件是 left >= right,因为是左闭右开,一个有效区间必须满足 left < right,区间里面才会有元素。)

看这个递归体里,我们用迭代器访问前序遍历的序列,迭代器不断往前移动,刚好把每个元素都访问了一遍。所以,整个算法的时间复杂度是 O(n)。

这个题目太简单了,我就不贴题目的原文了。意思是这样的,给你一个字符数组(字符串),然后,你要原地把这个数组的元素顺序反转。这道题目是非常平凡的,常规解法是使用双指针,头尾指针向中间夹逼,交换头尾指针指向的字符。

1
2
3
4
5
6
7
class Solution:
def reverseString(self, s: List[str]) -> None:
l, r = 0, len(s) - 1
while l < r:
s[l], s[r] = s[r], s[l]
l += 1
r -=

用 Python 写,会非常短小。时间复杂度是 O(n),空间复杂度是 O(1)。

假如,让你为这个题目设计一个递归算法,你会怎么写呢?

方案一:假设我们掌握了一个把下标 [i, j] 范围内的字符顺序反转的方法。

那么对于这个题目来说,我们只要交换头尾两个字符,然后,用递归方法去计算中间剩余部分即可。

1
2
3
4
5
6
7
class Solution:
def reverseString(self, s: List[str]) -> None:
def reverse(i: int, j: int) -> None:
if i < j:
s[i], s[j] = s[j], s[i]
reverse(i + 1, j - 1)
reverse(0, len(s) - 1

这个方法和上面双指针其实如出一辙。

方案二:深度优先搜索,从当前位置探索最后一个字符,找到后,把最后一个字符放到正确位置,然后回溯。

1
2
3
4
5
6
7
8
9
10
class Solution:
def reverseString(self, s: List[str]) -> None:
n = len(s)
def dfs(i: int):
if i == n:
return
c = s[i]
dfs(i + 1)
s[n - 1 - i] = c
dfs(0

这里很有意思的一点,就是这个变量 c 可不可以不要?为什么?

你还能想出其他的递归设计方法么?欢迎给我留言。

这是今天的打卡题目,看标题,就知道这是系列题目,不过那不重要的。我们先来看看题目:

给你一个由 不同 整数组成的数组 nums ,和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。

题目数据保证答案符合 32 位整数范围。

示例 1:
输入:nums = [1,2,3], target = 4
输出:7
解释:
所有可能的组合为:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意,顺序不同的序列被视作不同的组合。

示例 2:
输入:nums = [9], target = 3
输出:0

提示:
1 <= nums.length <= 200
1 <= nums[i] <= 1000
nums 中的所有元素 互不相同
1 <= target <= 1000

  1. 组合总和IV <-- 传送门
阅读全文 »

如果说,2~3 个月前,这种题我是不可能做出来的,不知道你信不信,现在总算是稍微觉得经过自己努力我也可以做出来了。看来这个还需要坚持和训练,就可以克服的。

阅读全文 »

通常,正整数 n 的阶乘是所有小于或等于 n 的正整数的乘积。例如,factorial(10) = 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1。

相反,我们设计了一个笨阶乘 clumsy:在整数的递减序列中,我们以一个固定顺序的操作符序列来依次替换原有的乘法操作符:乘法(*),除法(/),加法(+)和减法(-)。

例如,clumsy(10) = 10 * 9 / 8 + 7 - 6 * 5 / 4 + 3 - 2 * 1。然而,这些运算仍然使用通常的算术运算顺序:我们在任何加、减步骤之前执行所有的乘法和除法步骤,并且按从左到右处理乘法和除法步骤。

另外,我们使用的除法是地板除法(floor division),所以 10 * 9 / 8 等于 11。这保证结果是一个整数。

实现上面定义的笨函数:给定一个整数 N,它返回 N 的笨阶乘。

示例 1:
输入:4
输出:7
解释:7 = 4 * 3 / 2 + 1

示例 2:
输入:10
输出:12
解释:12 = 10 * 9 / 8 + 7 - 6 * 5 / 4 + 3 - 2 * 1

  1. 笨阶乘 <— 传送门
阅读全文 »

这道题目的意思是,计算每个数字的二进制表示里 1 的数量。其实,计算方法,也比较简单,就是写个循环,计算当前循环中的数字的 bit 位数。怎么计算一个数字的 bit 里的 1 的位数呢?

我想到的方法很简单,就是使用 “位与” 计算,一个整数,与 1 进行 & 运算,结果 1,说明最低位是 1,结果是 0,说明最低位是 0。然后,我们把这个数字往右移 1 位。重复这个过程,直到这个数字变为 0。就统计出了所有的 1 的数量。

然后我写出了这个算法:

1
2
3
4
5
6
7
8
9
10
11
class Solution:
def countBits(self, num: int) -> List[int]:
res = []
for i in range(num + 1):
cnt = 0
n = i
while n > 0:
cnt += n & 1
n = n >> 1
res.append(cnt)
return res

这个算法的复杂度是多少呢?第一重循环是 n 次,第二重循环最多是 log2(n)次,随着数字的缩小,次数还会减少。具体就比较复杂了:[
O(\sum_{i=1}^{n}\log_2i)
]但是,原来题目里有个提示,就是,它问能不能用 O(n) 的算法计算出来。还提示了一句,算法的空间复杂度是 O(n)。你看,上面那个算法空间复杂度是 O(1) 的,没有用额外的空间。而现在明告诉你用 O(n),其实就是说这题目可以使用递推法。现在 LC 的人流行叫动态规划,不过,我觉得动态规划在这个场景里没有递推法听起来更明白。不过写起来是一回事。

什么是递推法,就是现在第 n 个解,可以用 n 以前的解推理得到。算是动态规划的特殊情况吧。不像动态规划理解起来那么抽象。当然,我说得头头是道的,当时看到题目的时候,脑子是空白的,这个读者你知道就行了。

其实,从我写的那个式子里就看出一种来。比如我用了移位操作,往右移位,其实就是除以 2 的意思。举个例子,假如我现在循环到 5 这个数字,最低位是个 1,然后往右移,继续循环,往右移后其实数字变成了 2,而刚才,其实计算过 2 里面的比特数的,但是在我的算法里,右继续计算了,如果我们不计算,而是查表所得,这里就不用循环了。不是么?

算法可以改改:

1
2
3
4
5
6
class Solution:
def countBits(self, num: int) -> List[int]:
res = [0]
for i in range(1, num + 1):
res.append(res[i >> 1] + (i & 1))
return res

这个算法意思就是,先计算最低位的 1 的数量,然后高位部分,查表就行了。有了这个算法,官方题解的另一个算法就不难理解了。既然我们可以把最低位和上面部分分开计算。显然也可以把最高位和下面部分分开。不过,不像最低位这么直观。

我们可以把一个数字分解成,最高位 1 和剩余部分,举个例子:假如 5 二进制表示是 101,可以分解为 101 = 100 + 1,高位是 4,剩余的是 1,也就是 5 是 4 的比特数加上 1 的比特数。计算到 5 的时候,前面 1 和 4 肯定早就计算出来了。4 是什么呢?就是 5 前面最近的一个 2 的整数次幂。而怎么判断一个数字是 2 的整数次幂呢?i & (i - 1) == 0,想明白了么?

具体完整算法我就不写了。去看官方解答或者自己写也不难。

这是今天的打卡题,说实在做得我实在是心态崩坏,先来看看题目,我再来细说:

给你一个嵌套的整型列表。请你设计一个迭代器,使其能够遍历这个整型列表中的所有整数。

列表中的每一项或者为一个整数,或者是另一个列表。其中列表的元素也可能是整数或是其他列表。

示例 1:

输入: [[1,1],2,[1,1]]
输出: [1,1,2,1,1]
解释: 通过重复调用 next 直到 hasNext 返回 false,next 返回的元素的顺序应该是: [1,1,2,1,1]。
示例 2:

输入: [1,[4,[6]]]
输出: [1,4,6]
解释: 通过重复调用 next 直到 hasNext 返回 false,next 返回的元素的顺序应该是: [1,4,6]。

  1. 扁平化嵌套列表迭代器 <-- 传送门 力扣(LeetCode)
阅读全文 »

这道题虽然是简单,但是一看这复杂的操作,我就彻底懵逼了。每次将 n-1 个数字加一,最后要所有的数字相等。

这是太抽象的一个过程,脑海里自然联想到了滑块拼图之类的东西,或者覆盖问题,想得极其复杂,所以马上就不知道怎么做了。然后还草稿上画了很多,找这个问题的规律。找了半天也没找到。

暴力解,就是照着题目意思去做,我们想到的就是贪心法,每次挑出最大的一个,其他都加一,然后重复这个过程,直到所有的都相等为止。我想到了这个算法,但是一时半会儿也不能证明这个就是正确的操作法,因题目要求最小的次数。谁知道贪心法的次数是不是最小呢?

所以我就看答案了,果然这个就是最小,有时候做算法题看来也只能靠大胆了。这种根本不用证明的。。。猜一个就是了。猜错就跪了呗。

然后我看到官方题解竟然想出了四种解题方法,第一种就是我说的暴力法,照字面意思硬做。果然,超时,因为是 O(n^2) 的解法啊,肯定过不了。然后第二种是,每次不是加一了,而是直接加 最大值与最小值的 diff,这样可以少加几次。你这么说我当然明白,但是怎么证明这个加法和原来那个加法是等价的呢?也是靠猜就行了?这并不显然啊!!

第三种解法是什么动态规划,我就更懵逼了,根本不是人话好不好,我至今也没看懂。直到最后一个解法出现,我才明白过来。不过官方题解仍然不是用人话写的,我看了一个网友用人话写了,才终于恍然大悟,原来这么简单。

把 n-1 个数字都加一,其实相当于把最大值减 1,这样每次操作 n - 1 个数的抽象复杂情况,变成了一个极其简单的情况,每次挑最大值减 1,这就太简单了。最少肯定是所有值都减到最小值就可以了。太牛了,于是,就是很容易写出一个 O(n) 算法了。在一次遍历中,找到最小值,顺便找出所有数字的和,然后做个减法就完事了。

1
2
3
4
5
6
7
class Solution:
def minMoves(self, nums: List[int]) -> int:
nums.sort()
res = 0
for i in reversed(range(1, len(nums))):
res += nums[i] - nums[0]
return res

最牛逼的 O(n) 算法我就不写了,大家自己写吧,上面这个是我写的 O(nlogn) 的算法,排序后,把所有数字和最小值的差求个和。

给我的启发:

  1. 试试逆向思维,不要忘记这一点;
  2. 虽然想明白后一点不难写,但是很多时候,题目难都在模型的转换上面,你看到的是假象。

今天的打卡题,是一道“困难”,先来看看题目:

给定一个字符串 s 和一个字符串 t ,计算在 s 的子序列中 t 出现的个数。

字符串的一个 子序列 是指,通过删除一些(也可以不删除)字符且不干扰剩余字符相对位置所组成的新字符串。(例如,“ACE” 是 “ABCDE” 的一个子序列,而 “AEC” 不是)

题目数据保证答案符合 32 位带符号整数范围。

  1. 不同的子序列 <-- 传送门

具体的例子,我都略去了,因为博客的排版比较弱,没法很好展示。其实,这道题目一看,就隐含了动态规划的气味,比如,求解的是个数,而不是具体的位置,第二,隐含了大量的穷举,才能进行的统计。

不过,如果你跟我一样小白的话,就会发现,你根本写不出状态转移的方程的,因为这个状态转移方程非常地不显然。

当然了,无论你想怎么去解决这道题目,首先还是要自己看懂题目。我们看看如何确定 t 在 s 中出现的次数。举个例子,假如 s = ababc,t = abc,那么很显然,t 在 s 出现了三次。然后我们来理一下,怎么统计。首先,我们把 t 的第一个字符 a,在 s 中标定,然后,是 b 标定,最后是 c,当 a 固定在第一个字符的时候,b 其实有两个选择。这两个选择的 b 都对应着唯一的 c,所以有两次,而 a,还有另一个选择,但是选那个 a 的时候,b,c 都只有唯一选择了,所以,总次数就是 3 次。

我上面描述的这个过程,就是一种最直观的统计策略。逐个标定 t 的每个字符,而且要穷尽每个字符的多个位置选择。这个就是一个比较明显的回溯过程。所以,很自然,我写出了回溯算法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
def numDistinct(self, s: str, t: str) -> int:
self.res = 0
self.dfs(s, t, 0)
return self.res

def dfs(self, s: str, t: str, p: int) -> None:
if len(t) == 1:
self.res += s[p:].count(t)
return

for i in range(p, len(s)):
if s[i] == t[0]:
self.dfs(s, t[1:], i + 1)

虽然是一道困难题,但是解法却很短小嘛,这个算法,每成功标定一个 t 的字符,就把 t 截短一截,然后继续向前扩展。这里有很低效的地方,比如每次截短 t,以及每次拷贝 s 之类的,容我偷个懒。

这个算法通过了 87% 的用例,说明,这是一个正确的算法,但是时间复杂度过高了。可以简单分析一下递归算法的时间复杂度,函数体内部,最坏情况循环大约是 len(s) - len(t) 次,而没深入一层,s 和 t 各减少了 1 (t 截短了 1 个字母,s 的下标后移了一个)。所以,然后把每层乘起来,综合复杂度是 O((m - n)!) 的复杂度。难怪过不了。

很容易想到,这个算法的优化空间,就是引入缓存,对中间结果进行记录,可以大幅减少搜索的数量。让我们来优化一下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
def numDistinct(self, s: str, t: str) -> int:
self.s, self.t = s, t
self.m, self.n = len(s), len(t)
self.mem = {}
return self.dfs(0, 0)

def dfs(self, p: int, q: int) -> int:
if self.m - p < self.n - q:
return 0

# 缓存
k = (p, q)
v = self.mem.get(k, -1)
if v > 0:
return v

if q == self.n - 1:
v = self.s[p:].count(self.t[-1])
self.mem[k] = v
return v

total = 0
for i in range(p, self.m):
if self.m - i >= self.n - q and self.s[i] == self.t[q]:
total += self.dfs(i + 1, q + 1)

self.mem[k] = total
return total

然后,我优化出了这个算法:

  1. 不在使用字符串作为参数,只是使用下标,避免了字符串拷贝
  2. 改换了函数的返回值,使得方便去缓存
  3. 引入了缓存来记录结果
  4. 如果 s 长度小于 t 显然就不用继续搜索了,可以直接剪枝

这么多优化后,总共 62 个用例,过了 61 个,好消息是优化是有效的,效率提高了很多。坏消息是,仍然 TLE。这给我们最大的提示就是,非多项式时间的算法,无论怎么优化,在足够大的问题规模面前,就是无法有效运算。哈!

还是要使用递推方法,用动态规划来解,一个是不用递归,省去了栈的开销,另一个就是放弃了大量无效的搜索。但是写不出状态转移方程怎么办?不要急,仔细观察一下咱们优化后的算法。

为了避免拷贝字符串,我们用 p 和 q,记录了 s 和 t 的下标搜索位置,从上述算法里,我们能看到 dfs(p, q) 其实就是 dfs(i + 1, q + 1) 当 s[i] == t[q] 时,i 的取值范围是 [p, m)。这几乎就是状态转移方程了。

第一版状态转移方程:[
f(i, j) = \left {

\right.
]

现在这个方程基本上是没法写出代码来的,基本上是递归搜索方法的原本表达,一个是里面有个求和公式,就算写出来,算法的时间复杂度也是O(n^3)的,另一个就是,在 s[i] != t[j] 的时候,没有写出方程。这时候,我们就要耐心下来深入研究一下,怎么把这个状态方程给写完整了。

再来观察一下 dfs 的实现,在 for 循环里,套了一个 if,所以我们直接写出了 s[i] == t[j] 时候的情况,if 的 else 子句,代码里没写,其实就是 s[i] != t[j] 时的状态转移,我们发现,其实 else 的情况,就是跳过了这个下标,直接从下一个重复这个扫描过程了。相当于是调用了 dfs(i + 1, j) 了。这里可以品味一下。

然后在看怎么解决那个求和公式,其实解决起来也不难,就是咱们可以展开这个求和公式来看看:[

]

不知道这么解释,容易理解么?这里我们用了一个数列求和的小技巧,就是错位相减,然后得到了 f(i,j) 的递推公式,到此,我们就构造了我们的第二版状态转移方程:[
f(i, j) = \left {

\right.
]

有了状态转移公式,我们还要处理好边界条件,当 j = len(t) - 1 的时候,f(i, j) 的值,其实就是那个字符出现的次数。所以,我们可以把 i 从 0 到 len(s) 的值,初始化成在这个范围内搜索 t 的最后一个字符的出现次数。而实际上,更抽象地看,可以理解成,空串出现的次数。因为空串是任何串的子串,所以空串都会出现 1 次。当然,这个结论并不显然,这可能需要一些证明,我们可以这么猜测,如果是对的就万事大吉了。毕竟我们不是在做数学证明。

另外一个边界,就是递归代码里也用到了,就是 s 剩余的长度小于 t 剩余的长度时,就不用扫描了,显然结果是 0 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
def numDistinct(self, s: str, t: str) -> int:
if len(s) < len(t):
return 0
dp = [[0] * len(t) for _ in range(len(s))]

for i in range(len(s)):
dp[i][len(t) - 1] = s[i:].count(t[-1])

for i in range(len(s) - 2, -1, -1):
for j in range(len(t) - 2, -1, -1):
if s[i] == t[j] :
dp[i][j] = dp[i + 1][j + 1] + dp[i + 1][j]
else:
dp[i][j] = dp[i + 1][j]
return dp[0][0]

我写出了这样的实现。7 - 8 行,可以用我说的更抽象的形式去替代,这样效率会更高一点。少了 len(s) 次的字符串统计行为。这个代码经测试是正确的。

总结,我通过这篇文章,从分析题目,到写出朴素的回溯算法,然后进行性能优化,发现了状态转移,并优化了状态转移方程,最终写出了动态规划算法。状态转移方程的物理意义,在优化过后已经变得比较模糊了,有时候强行去解释的话,,听起来很绕,而且一下子想看懂,恐怕也非常难。学习动态规划,不用去纠结这一点,不然真的会陷在里面。