完整解释

二、阅读程序

(1)

• 程序分析：该程序通过递归的方式，深度优先地搜索一个数组的所有子序列。solve(index, current_sum)函数的核心思想是对于 a[index] 这个元素，探索两种可能：选它（进入solve(index+1, current_sum + a[index])）或不选它（进入solve(index+1, current_sum)）。当遍历完所有元素 (index == n)，检查 current_sum 是否等于目标 S，如果是，则这条搜索路径贡献了1个方案。最终将所有方案数相加。
• 题目解析：
  1. 判断题 (假)：该程序是纯粹的递归搜索，它会重复计算相同的子问题（例如，从不同路径到达相同的index和current_sum）。因为它没有使用数组或哈希表来存储中间结果，所以它不是动态规划或记忆化搜索。
  2. 判断题 (真)：算法逻辑基于加法，对正数、负数和零都同样适用，不影响正确性。
  3. 判断题 (假)：在每一步递归中，函数都会分裂成两个调用。对于n个元素，递归树的深度为n，总的调用次数大约是 2^n。因此，时间复杂度为 O(2^n)，而非 O(n*S)。
  4. 选择题 (C)：程序递归地遍历了所有子序列的选择情况，并统计了和为S的子序列个数。
  5. 选择题 (B)：对于输入 4 5 和 1 2 3 4，程序会寻找和为 5 的子序列。通过穷举可以发现，满足条件的子序列只有 {1, 4} 和 {2, 3} 两个。因此，程序的正确输出应为 2。

(2)

• 程序分析：该程序构建了一个有向图，并使用深度优先搜索（DFS）结合记忆化（memo数组）来计算图中的最长路径。dfs(u) 计算从节点 u 出发能到达的最长路径的长度（以节点数为单位）。main 函数对每个节点都调用一次dfs，是为了确保能找到全局的最长路径，因为图可能是不连通的，或者最长路径的起点不确定。
• 题目解析： 6. 判断题 (假)：memo[u] 存储的是从节点 u 出发的最长路径长度，而不是到节点 u。 7. 判断题 (真)：如果图中有环（例如 A->B, B->A），dfs(A) 会调用 dfs(B)，而 dfs(B) 又会回头调用 dfs(A)，程序会因无限递归而栈溢出。该算法仅适用于有向无环图（DAG）。 8. 判断题 (真)：这就是该算法的准确描述。 9. 选择题 (C)：程序对每个节点 i 调用 dfs(i) 找到从它出发的最长路径，然后取所有这些值的最大值。这正是“有向无环图中所有节点作为起点的最长路径中的最大值”，即DAG的最长路径。 10. 选择题 (C)：分析图：0->1, 0->2, 1->3, 2->3, 3->4。 * dfs(4) 返回 1。 * dfs(3) 调用 dfs(4)，返回 1+1=2。 * dfs(1) 调用 dfs(3)，返回 1+2=3。 * dfs(2) 调用 dfs(3)，返回 1+2=3。 * dfs(0) 调用 dfs(1) 和 dfs(2)，取较大者，返回 1+3=4。 main 函数遍历所有节点作为起点，找到的最大值是 dfs(0) 的结果，即 4。

(3)

• 程序分析：这是一个典型的动态规划解法，用于解决最少硬币找零问题。dp[i] 表示凑出金额 i 所需的最少硬币数量。状态转移方程 dp[i] = min(dp[i], dp[i - coins[j]] + 1) 的含义是：要凑出金额 i，可以尝试使用一个 coins[j] 硬币，这要求我们已经知道了凑出 i - coins[j] 的最少硬币数，然后在这个基础上加一即可。
• 题目解析： 11. 判断题 (假)：dp[i] 的含义是组成金额 i 所需的最少硬币数量，而不是方案总数。 12. 判断题 (真)：对于求解最少硬币数（即求最优解），内外层循环的顺序不影响最终结果。两种顺序都能保证 dp[i] 在被计算时，所有依赖的子问题 dp[i - coin] 都已经计算完毕。 13. 判断题 (假)：去掉 + 1 后，状态转移变为 dp[i] = min(dp[i], dp[i - coins[j]])，这失去了递推累加的意义，其结果没有明确的组合意义。 14. 选择题 (C)：该问题允许每种硬币无限次使用，目标是求最少数量，是典型的找零钱问题。 15. 选择题 (B)：求凑出金额 6 所需的最少硬币数，硬币为{1, 3, 4}。 * dp[0]=0 * ... * dp[3]=1 (使用硬币3) * dp[6]=min(dp[5]+1, dp[3]+1, dp[2]+1)。通过计算可得 dp[6]=dp[3]+1=2 (使用两个硬币3)。最优解是 3+3，共2枚。

三、完善程序

(1) 合法括号序列

• 程序分析：利用栈的“后进先出”特性来匹配括号。遇到左括号就压栈；遇到右括号，就检查栈顶是否是对应类型的左括号，如果是就弹栈，如果不是或栈为空则序列非法。最后，如果栈为空，说明所有左括号都被成功匹配。
• 题目解析： 16. B: 遇到左括号，将其压入栈中等待匹配，即 st.push(c)。 17. C: 如果遇到右括号时栈是空的 (st.empty())，说明没有左括号与之匹配，序列非法。 18. C: st.top() 用于获取栈顶元素进行比较，但不会将其弹出。 19. D: 匹配成功后，栈顶的左括号需要被弹出，表示一对括号已闭合，即 st.pop()。 20. C: 遍历完整个字符串后，栈必须为空 (st.empty()) 才说明所有左括号都找到了匹配，序列才合法。如果栈非空，则说明有未闭合的左括号。

(2) 合并区间

• 程序分析：该算法首先按区间的起始位置排序。然后，它维护一个 merged 列表。遍历排序后的区间，如果当前区间与 merged 的最后一个区间重叠，则更新 merged 最后一个区间的结束位置；否则，说明遇到了一个新的不重叠区间，直接将其加入 merged 列表。
• 题目解析： 21. C: merged 列表用排序后的第一个区间 intervals[0] 进行初始化。 22. B: 判断重叠的条件是，当前区间的起始点 intervals[i].first 小于或等于 merged 最后一个区间的结束点 merged.back().second。 23. D: 发生重叠时，需要更新 merged 最后一个区间的结束点 (merged.back().second)，新结束点应该是它原来的结束点和当前区间结束点中的较大值。 24. A: 如果不重叠，直接将当前区间 intervals[i] 作为一个新的、独立的区间添加到 merged 列表中。