给定一个整数数组 nums，找到其中最长的严格上升子序列的长度。

子序列是指从原数组中删除一些元素（或不删除）后，剩余元素保持原有顺序的序列。

要求：

子序列必须是严格上升的（即每个元素都比前一个元素大）。

返回最长严格上升子序列的长度。

横线处应该填写的是（）

def length_of_lis(nums):
	if not nums:
		return 0

	dp = [1] * len(nums)
	for i in range(1, len(nums)):
		for j in range(i):
			if nums[j] < nums[i]:
				________________
	return max(dp)

下面程序的时间复杂度是（）

def func(n):
	for i in range(n):
		for j in range(i, n):
			print(i, j)

pow(10, log10(100))的值是

以下代码的功能是什么？

def fuction1(text1, text2):
	m, n = len(text1), len(text2)
	dp = [[0] * (n + 1) for _ in range(m + 1)]
	for i in range(1, m + 1):
		for j in range(1, n + 1):
			if text1[i - 1] == text2[j - 1]:
				dp[i][j] = dp[i - 1][j - 1] + 1
			else:
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
	return dp[m][n]

以下代码的功能是什么？

def max_subarray(nums):
	dp = [0] * len(nums)
	dp[0] = nums[0]
	for i in range(1, len(nums)):
		dp[i] = max(nums[i], dp[i - 1] + nums[i])
	return max(dp)

[10, 9, 2, 5, 3, 7, 101, 18]，最长的严格上升子序列是（）

以下代码的功能是什么？

def knapsack(weights, values, capacity):
	n = len(weights)
	dp = [[0] * (capacity + 1) for _ in range(n + 1)]
	for i in range(1, n + 1):
		for j in range(1, capacity + 1):
			if weights[i - 1] <= j:
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i
- 1])
			else:
				dp[i][j] = dp[i - 1][j]
	return dp[n][capacity]

以下代码的时间复杂度是多少？

def fib(n):
	if n <= 1:
		return n
	return fib(n - 1) + fib(n - 2)

给定一个无向图，图的节点编号从 0 到 n-1，图的边以邻接表的形式给出。编写的一个python程序，使用深度优先搜索（DFS）遍历该图，并输出遍历的节点顺序。

下面程序中横线处应该填写的是（）

def dfs(graph, start, visited=None):
	if visited is None:
		visited = set()
	visited.add(start)
	print(start, end=" ")

	for neighbor in graph[start]:
		if neighbor not in visited:
			________________

graph = {
	0: [1, 2],
	1: [0, 3, 4],
	2: [0, 5],
	3: [1],
	4: [1, 5],
	5: [2, 4]
}

print("DFS 遍历顺序:")
dfs(graph, 0)

以下代码输出的是什么（）

class A:
	def __init__(self):
		self.x = 1

class B(A):
	def __init__(self):
		super().__init__()
		self.y = 2

b = B()
print(b.x, b.y)

以下代码的功能是什么？

def coin_change(coins, amount):
	dp = [float('inf')] * (amount + 1)
	dp[0] = 0
	for coin in coins:
		for i in range(coin, amount + 1):
			dp[i] = min(dp[i], dp[i - coin] + 1)
	return dp[amount] if dp[amount] != float('inf') else -1

exp(log(2))的值是（）

以下代码的时间复杂度是多少？

def fib(n, memo={}):
	if n <= 1:
		return n
	if n not in memo:
		memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
	return memo[n]

以下代码的功能是什么？

def unique_paths(m, n):
	dp = [[1] * n for _ in range(m)]
	for i in range(1, m):
		for j in range(1, n):
			dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
	return dp[m - 1][n - 1]

下列哪个选项是python中的关键字？

表达式 1e6 、 1000000 和 10^6 的值是相同的。

动态规划算法通常有递归实现和递推实现。但由于递归调用在运行时会由于层数过多导致程序崩溃，因此有些动态规划算法只能用递推实现。

一颗 层的满二叉树，一定有 个结点。

使用了math模块中的表达式 cos(60) 的结果类型为 float 、值约为 0.5 。

快速排序一般是不稳定的。

邻接表和邻接矩阵都是图的存储形式。为了操作时间复杂度考虑，同一个图可以同时维护两种存储形式。

子类对象包含父类的所有成员（包括私有成员）。从父类继承的私有成员也是子类的成员，因此子类可以直接访问。

按照下面的规则生成一棵二叉树：以一个人为根节点，其父亲为左子节点，母亲为右子节点。对其父亲、母亲分别用同样规则生成左子树和右子树。以此类推，记录30代的直系家谱，则这是一棵满二叉树。

在python语言中，函数调用前必须有函数声明或定义。

int 类型能表达的数都能使用 float 类型精确表达。

图上移动

题目描述

小 A 有一张包含n 个结点与 m条边的无向图，结点以1,2,...,n 标号。小 A 会从图上选择一个结点作为起点，每一步移动到某个与当前小 A 所在结点相邻的结点。对于每个结点 i（1≤i≤n ），小 A 想知道从结点i 出发恰好移动1,2,...,k步之后，小 A 可能位于哪些结点。由于满足条件的结点可能有很多，你只需要求出这些结点的数量。

输入格式

第一行，三个正整数 n,m,k，分别表示无向图的结点数与边数，最多移动的步数。

接下来m 行，每行两个正整数 ui,vi，表示图中的一条连接结点 ui与vi 的无向边。

输出格式

共n 行，第 i行（1≤i≤n  ）包含 k个整数，第j 个整数（1≤j≤k  ）表示从结点 i出发恰好移动j 步之后可能位于的结点数量。

输入样例

4 4 3
1 2
1 3
2 3
3 4

输出样例

2 4 4
2 4 4
3 3 4
1 3 3

数据范围

对于20 % 的测试点，保证k=1 。

对于另外20 % 的测试点，保证 1≤n≤50，1≤m≤50 。

对于所有测试点，保证 1≤n≤500，1≤m≤500 ，1≤k≤20 ，1≤ui,vi≤n。

等价消除

题目描述

小 A 有一个仅包含小写英文字母的字符串 S。

对于一个字符串，如果能通过每次删去其中两个相同字符的方式，将这个字符串变为空串，那么称这个字符串是可以被等价消除的。

小 A 想知道 S有多少子串是可以被等价消除的。

一个字符串 S'是S 的子串，当且仅当删去 S的某个可以为空的前缀和某个可以为空的后缀之后，可以得到 S'。

输入格式

第一行，一个正整数|S| ，表示字符串S 的长度。

第二行，一个仅包含小写英文字母的字符串 S。

输出格式

一行，一个整数，表示答案。

输入样例 1

7
aaaaabb

输出样例 1

9

输入样例 2

9
babacabab

输出样例 2

2

数据范围

对于20 % 的测试点，保证S 中仅包含 a 和 b 两种字符。

对于另外20 % 的测试点，保证 1≤|S|≤2000。

对于所有测试点，保证 1≤|S|≤2*105 。