首页 › 题库 › GESP编程能力等级认证 › 4 简单动态规划

GESP-Python六级 题库

共 18 道题 · 按题型筛选,点「查看答案」核对解析
章节 4 简单动态规划 清除
1 单选题 适中 GESP编程能力等级认证 ·GESP-Python六级 · 4.1 一维动态规划

小朋友们去邻里拜年,每个家里有不同数量的糖果。规则是:不能连续进入两个相邻的房子(即不能同时取相邻两家的糖果)。目标是拿到最多糖果。以下是代码实现,请补全横线。

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

    size = len(nums)
    if size == 1:
        return nums[0]

    dp = [0] * size
    dp[0] = nums[0]
    dp[1] = max(nums[0], nums[1])

    for i in range(2, size):
        dp[i] = max(dp[i-1], dp[i-2] + nums[i])  # 填空处

    return dp[size - 1]

if __name__ == "__main__":
    nums1 = [1, 2, 3, 1]
    print(visit(nums1))

    nums2 = [2, 7, 9, 3, 1]
    print(visit(nums2))

    nums3 = [5]
    print(visit(nums3))

    nums4 = []
    print(visit(nums4))


A
dp [i] = dp [i - 1] + nums [i]
B
dp [i] = max (dp [i - 1], dp [i - 2] * nums [i])
C
dp [i] = max (dp [i - 1], dp [i - 2] + nums [i])
D
dp [i] = dp [i - 2] + nums [i]
答案与解析
正确答案:C
定义状态 dp[i] 表示前 i+1 间房子可获得的最大糖果数。初始化处理空数组和单个元素情况。dp[0] 为第一间房子的糖果数,dp[1] 为前两间中较大值。从第三间开始,每间房子有两种选择:不进入则继承 dp[i-1];进入则加上当前糖果数 nums[i] 并加上 dp[i-2]。状态转移需取两者最大值。遍历完成后,最后位置的 dp 值即为全局最优解。
题目详情
2 单选题 适中 GESP编程能力等级认证 ·GESP-Python六级 · 4.1 一维动态规划

元宵节晚上,小朋友沿着一条发光石板路前进,每次可以向前走1 块或2 块石板。若dp[i] = dp[i - 1]+ dp[i - 2],下面关于dp[i] 的含义最合适的是()。

A
走到第i 块石板的不同走法数量
B
走到第i 块石板时,已经走过的石板总数
C
从第i 块石板走回起点的最少步数
D
从第i 块石板走回起点的最大步数
答案与解析
正确答案:A
分析递推关系 dp[i] = dp[i-1] + dp[i-2] 的构成机制。当前状态的值由前两个状态的值相加得到,表明每一步的结果依赖于前两步结果的累积。考虑行走过程中的选择:到达第 i 块石板的方式可以从第 i-1 块走1步,或从第 i-2 块走2步。因此,到达第 i 块的路径数等于到达前两块石板路径数之和。该递推形式与路径计数问题中的状态转移一致,反映的是不同决策路径的叠加方式。
题目详情
3 单选题 适中 GESP编程能力等级认证 ·GESP-Python六级 · 4.1 一维动态规划

0/1 背包(每件物品最多选一次) 问题通常可用一维动态规划求解 ,核心代码如下 。遍历的方向无所谓 ,则下面说法正确的是(  )。

def zero_one_knapsack(items, W): 
    dp = [0] * (W + 1) 
    for w, v in items: 
        for j in range(W, w - 1, -1): 
            dp[j] = max(dp[j], dp[j - w] + v) 
    return dp[W]
A

内层 j 必须从小到大,否则会漏解

B

内层 j 必须从大到小,否则同一件物品会被用多次

C

j 从大到小或从小到大都一样

D

只要 dp 初始为 0 ,方向无所谓

答案与解析
正确答案:B
动态规划数组 dp 表示容量为 j 时能获得的最大价值。每件物品仅可选择一次,更新状态时需确保当前物品的重量和价值不会基于本轮已更新的状态进行计算。内层循环遍历容量从 W 到 w,采用逆序确保每次状态转移依赖的是前一轮物品的 dp 值。若采用正序,则较小容量的状态先被更新,后续较大容量可能重复引用同一物品,导致物品被多次使用。逆序避免了当前轮次的状态覆盖对后续状态转移的影响。
题目详情
4 单选题 适中 GESP编程能力等级认证 ·GESP-Python六级 · 4.1 一维动态规划

以下关于动态规划的说法中,错误的是( )。

A

动态规划方法通常能够列出递推公式。

B

动态规划方法的时间复杂度通常为状态的个数。

C

动态规划方法有递推和递归两种实现形式。

D

在使用动态规划思想(即避免重复子问题)的前提下,递推实现与递归实现(记忆化搜索)的时间复杂度通常是相当的。

答案与解析
正确答案:B
动态规划通过定义状态描述问题的子结构,建立状态之间的转移关系形成递推公式。状态数量决定计算过程中需要处理的子问题总数。实现时可采用自底向上的递推方式,按顺序求解每个状态;也可采用自顶向下的递归方式配合记忆化存储,避免重复计算相同状态。两种实现方式均覆盖全部必要子问题,访问的状态集合一致,执行的操作规模由状态空间和转移成本共同决定。算法的时间开销取决于状态总数与单个状态转移所需时间的乘积。
题目详情
5 单选题 适中 GESP编程能力等级认证 ·GESP-Python六级 · 4.1 一维动态规划

以下关于动态规划算法特性的描述,正确的是( )。

A

子问题相互独立,不重叠

B

问题包含重叠子问题和最优子结构

C

只能从底至顶迭代求解

D

必须使用递归实现,不能使用迭代

答案与解析
正确答案:B
这道题暂未补解析。
题目详情
6 单选题 适中 GESP编程能力等级认证 ·GESP-Python六级 · 4.1 一维动态规划

给定"个物品和一个最大承重为w的背包 ,每个物品有一个重量wuti和价值oalli ,每个物品只能选择放或不放 。 目标是选择若干个物品放入背包 ,使得总价值最大 ,且总重量不超过 。关于下面代码 ,说法正确的是  ()  。

def knapsack1D(W: int, wt: list[int], val: list[int], n: int) -> int:
    dp = [0] * (W + 1)
    for i in range(n):
        for w in range(W, wt[i] - 1, -1):
            dp[w] = max(dp[w], dp[w - wt[i]] + val[i])
    return dp[W]
A
该算法不能处理背包容量为 0 的情况
B
外层循环 i 遍历背包容量, 内层遍历物品
C
从大到小遍历 w 是为了避免重复使用同一物品
D
这段代码计算的是最小重量而非最大价值
答案与解析
正确答案:C
这道题暂未补解析。
题目详情
7 单选题 适中 GESP编程能力等级认证 ·GESP-Python六级 · 4.1 一维动态规划

关于动态规划的描述,正确的是( )。

A
动态规划算法的时间复杂度总是低于贪心算法。
B
动态规划要求问题必须具有最优子结构和重叠子问题两个性质。
C
动态规划通过递归实现时不需要存储中间结果。
D

动态规划的核心思想是将问题分解为互不重叠的子问题。

答案与解析
正确答案:B
这道题暂未补解析。
题目详情
8 单选题 适中 GESP编程能力等级认证 ·GESP-Python六级 · 4.1 一维动态规划

以下代码实现了0/1背包问题的动态规划解法。假设物品重量为 weights[] ,价值为 values[] ,背包容量为 W ,横线上应填写( )。

def knapsack(W, weights, values):
	n = len(weights)
	dp = [[0] * (W + 1) for _ in range(n + 1)]

	for i in range(1, n + 1):
		for j in range(1, W + 1):
			if weights[i - 1] > j:
				dp[i][j] = dp[i - 1][j]
			else:
				dp[i][j] = max(__________________________________)
	return dp[n][W]
A
dp[i][j], dp[i - 1][j - weights[i - 1]] + values[i - 1]
B
dp[i - 1][j], dp[i][j - weights[i - 1]] + values[i - 1]
C
dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1]
D
dp[i - 1][j], dp[i - 1][j - weights[i]] + values[i]
答案与解析
正确答案:C
这道题暂未补解析。
题目详情
9 单选题 适中 GESP编程能力等级认证 ·GESP-Python六级 · 4.1 一维动态规划

动态规划通常用于解决( )。

A
无法分解的问题
B
可以分解成相互依赖的子问题的问题
C
可以通过贪心算法解决的问题
D
只能通过递归解决的问题
答案与解析
正确答案:B

一个问题是否能用DP来解决我们的考虑一般有两点:① 最优子结构,②无后效性最优子结构即 选项B,可分解成相互依赖的子问题的问题,因此选B。

题目详情
10 单选题 适中 GESP编程能力等级认证 ·GESP-Python六级 · 4.1 一维动态规划

阅读以下用动态规划解决的0-1背包问题的函数,假设背包的容量 W WW 是10kg,假设输入4个物品的重量 w e i g h t s weightsweights 分别为 1,3,4,6(单位为kg),每个物品对应的价值 v a l u e s valuesvalues 分别为 20,30,50,60,则函数的输出为( )。

def knapsack(capacity, weights, values):
	dp = [[0 for _ in range(capacity + 1)] for _ in range(len(weights) + 1)]
	for i in range(1, len(weights) + 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[-1][-1]
	
weights = [1, 3, 4,6]
values = [20,30,50,60]
capacity = 10
print(knapsack(capacity, weights, values))
A
90
B
100
C
110
D
140
答案与解析
正确答案:C

01背包问题,dp[n][w]表示将前n个物品放入容量为w的背包中得到的最大价值,4个物品的重量为1 3 4 6,价值为20 30 50 60,背包容量为10,最大价值是1 3 6 对应的110。

题目详情
11 判断题 偏易 GESP编程能力等级认证 ·GESP-Python六级 · 4.1 一维动态规划

以下代码实现了0 -1背包问题的一维动态规划解法,内层循环采用经典的逆序遍历方式。若将内层循环改为正序遍历(即for j in range(w[i], W + 1):),仍能得到正确答案。

def knapsack_01():
    W = 5
    w = [2, 3, 4]
    v = [10, 1, 1]
    n = 3
    dp = [0] * (W + 1)

    for i in range(n):
        for j in range(W, w[i] - 1, -1):
            dp[j] = max(dp[j], dp[j - w[i]] + v[i])

    print(dp[W])

knapsack_01()


A
对
B
错
答案与解析
正确答案:错
分析二维状态转移方程在压缩为一维时的状态更新顺序。逆序遍历确保每次更新依赖的是上一轮的状态值,避免同一物品被重复选择。正序遍历会使用本轮已更新的状态值,导致状态依赖发生改变。当物品重量与价值关系满足特定条件时,正序可能恰好得到相同结果。需验证每轮状态更新过程中对dp[j]的访问是否覆盖了所有必要情况。比较两种遍历方式下每个j位置的来源状态是否等价。检查物品不可拆分的前提下,容量递增或递减更新对状态覆盖的影响。
题目详情
12 判断题 偏易 GESP编程能力等级认证 ·GESP-Python六级 · 4.1 一维动态规划

在动态规划问题中,状态空间相同且没有重复计算的情况下,“状态转移方程+递推”与“递归+记忆化搜索”的时间复杂度通常相同。

A
对
B
错
答案与解析
正确答案:对
比较两种实现方式的时间复杂度需分析其基本机制。状态转移方程配合递推按确定顺序遍历状态空间,每个状态仅计算一次。递归结合记忆化搜索在访问某状态时若未计算则求值并存储,后续直接查表。两者均保证每个状态被处理且仅被处理一次。时间消耗主要来自状态数量及单个状态的转移开销。只要状态空间一致且无冗余计算,执行的操作总量由状态数和转移关系决定,与实现形式无关。算法结构差异不影响总操作次数的理论下限。
题目详情
13 判断题 偏易 GESP编程能力等级认证 ·GESP-Python六级 · 4.1 一维动态规划

下面代码实现了动态规划版本的斐波那契数列计算,其时间复杂度是。

A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
题目详情
14 判断题 偏易 GESP编程能力等级认证 ·GESP-Python六级 · 4.1 一维动态规划

下面代码采用动态规划求解零钱兑换问题:给定n种硬币,第i 种硬币的面值为coins[i-1] ,目标金额为amt,每种硬币可以重复选取,求能够凑出目标金额的最少硬币数量;如果不能凑出目标金额,返回 -1 。

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
15 判断题 偏易 GESP编程能力等级认证 ·GESP-Python六级 · 4.1 一维动态规划

在动态规划解决一维硬币找零问题时,若硬币面额为 [1, 3, 4] ,目标金额为 6 ,则最少需要 2 枚硬币(3+3)。

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
16 判断题 偏易 GESP编程能力等级认证 ·GESP-Python六级 · 4.1 一维动态规划

状态转移方程是动态规划的核心,可以通过递推方式表示问题状态的变化。

A
对
B
错
答案与解析
正确答案:对

状态转移方程是动态规划中表示状态变化的核心公式。

题目详情
17 判断题 偏易 GESP编程能力等级认证 ·GESP-Python六级 · 4.1 一维动态规划

应用动态规划算法时,识别并存储重叠子问题的解是必须的。

A
对
B
错
答案与解析
正确答案:对

动态规划算法通过存储重叠子问题的解来避免重复计算,提高效率。正确

题目详情
18 判断题 偏易 GESP编程能力等级认证 ·GESP-Python六级 · 4.1 一维动态规划

TCP/IP的传输层的两个不同的协议分别是UDP和TCP。

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情