笔试时间：2025年9月21日

往年笔试合集：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题

新郎为迎接新娘，需要面对 n 个伴娘的拦截。新郎每次从当前位置选择下一步移动到后面第一个或者第二个伴娘处，但是移动前需要给出当前位置伴娘所需金额红包 cost[n]。

请设计一段程序，帮助新郎计算一下，如何用最小金额的红包到达新娘面前。

假设：

• 给出 n+1 个正整数，第一个数字代表伴娘的总个数，第二个数字开始，每个数字分别代表此位置上伴娘需要的红包的金额 cost[n]。
• 一旦新郎支付了此位置伴娘的红包，即可选择向前，然后面对后面下一个或者再下一个伴娘的拦截，若没有再下一个伴娘，则成功到达新娘面前。

输入描述

输入为一串数字，第一个数字代表伴娘的总个数，第二个数字开始每个数字代表一个伴娘需要的红包金额。

提示：

• 2 ≤ n ≤ 1000
• 1 ≤ cost[i] ≤ 1000

输出描述

输出为一个数字，即新郎需要支付的最小红包总金额

样例输入

3 5 10 15

样例输出

10

样例说明1

一共有3个伴娘，第一个需要5元红包，第二个需要10元红包，第三个需要15元红包。新郎开始可以花费0，直接选择走到第二个伴娘面前。然后支付10元红包后向前继续，因为后面只有一个伴娘，不存在再下一个伴娘，所以总红包10元即可到达新娘面前。

参考题解

解题思路：

1. 定义状态：创建一个数组 dp，其中 dp[i] 表示到达第 i 个伴娘位置（从0开始计数）所需的最小红包金额
2. 状态转移：到达第 i 个伴娘的路径只有两种可能： 从第 i-1 个伴娘处跳一步过来，花费为 dp[i-1] + cost[i-1]从第 i-2 个伴娘处跳两步过来，花费为 dp[i-2] + cost[i-2]因此，dp[i] 就是这两者中的较小值
3. 初始化：新郎开始时在所有伴娘之前，他可以选择直接走到第一个或第二个伴娘面前，这个过程不产生花费。所以 dp[0] 和 dp[1] 都初始化为0
4. 计算结果：最终结果是在"到达最后一个伴娘的花费+最后一个伴娘的红包"与"到达倒数第二个伴娘的花费+倒数第二个伴娘的红包"中取一个最小值

C++：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    while (cin >> n) {
        vector<int> cost(n);
        for (int i = 0; i < n; i++) {
            cin >> cost[i];
        }
        
        if (n < 2) {
            if (n <= 0) {
                cout << 0 << endl;
            } else {
                cout << cost[0] << endl;
            }
            continue;
        }
        
        vector<int> dp(n);
        dp[0] = 0;
        dp[1] = 0;
        
        for (int i = 2; i < n; i++) {
            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }
        
        int result = min(dp[n - 1] + cost[n - 1], dp[n - 2] + cost[n - 2]);
        cout << result << endl;
    }
    
    return 0;
}

Java：

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextInt()) {
            int n = scanner.nextInt();
            int[] cost = new int[n];
            for (int i = 0; i < n; i++) {
                cost[i] = scanner.nextInt();
            }
            
            if (n < 2) {
                if (n <= 0) {
                    System.out.println(0);
                } else {
                    System.out.println(cost[0]);
                }
                continue;
            }
            
            int[] dp = new int[n];
            dp[0] = 0;
            dp[1] = 0;