💻 ACM金牌团队🏅️ | 多次AK大厂笔试 ｜ 大厂实习经历

👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸

✨ 笔试合集传送们 -> 🧷学长刷题笔记

🍒 本专栏已收集 140+ 套题 🍄 题面描述等均已改编，如果和你实际看到的题面描述不一样请理解，做法和题目本质基本不变。

🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力 💞

💌 01.硬币最少组合问题

问题描述

K小姐有一个爱好就是收集各种硬币。有一天，她在整理自己的硬币收藏时，突然想到了一个有趣的问题。如果给定一个总金额 ，能够用手上现有的硬币面值组合成该金额，需要的硬币数量最少是多少枚呢？

现在已知K小姐有 种不同面值的硬币，分别为 、、、、、、 元，每种面值的硬币数量都是无限的。请你帮助K小姐设计一个程序，快速计算出给定总金额所需的最少硬币组合。

输入格式

输入仅包含一个正整数 ，表示要求组合的目标总金额，单位为元。

输出格式

输出最少硬币组合，从大到小按面值顺序输出，硬币面值间用空格分隔。若无法用现有面值组合出目标总金额，则输出 。

样例输入

8

样例输出

5 2 1

数据范围

题解

这是一个典型的动态规划问题。可以定义一个一维数组 ，其中 表示组合成金额 所需的最少硬币数量。

先将 数组初始化为一个较大的值，表示暂时无法组合出该金额。然后对于每一种面值的硬币，遍历 ，尝试更新 的值。具体来说，对于面值为 的硬币，可以将金额 拆分为 和 两部分，即 ，表示组合成金额 的最少硬币数等于组合成金额 的最少硬币数再加上当前这枚面值为 的硬币。

最后，再从 开始回溯，找出凑成总金额的硬币组合方案。具体做法是，从 开始，如果 ，即找到了上一个状态，就将两个状态的差值 加入答案数组中，然后令 ，直到 减小到 为止。因为要求输出的硬币面值要从大到小排列，所以最后再对答案数组逆序输出即可。

参考代码

• Python

import sys

n = int(sys.stdin.readline().strip())
coins = [1, 2, 5, 10, 20, 50, 100]
INF = float('inf')

dp = [INF] * (n + 1)
dp[0] = 0

for val in coins:
    for j in range(val, n + 1):
        dp[j] = min(dp[j], dp[j - val] + 1)

if dp[n] == INF or n == 0:
    print(-1)
    exit(0)

result = []
last, j = n, n
while j >= 0:
    if dp[j] == dp[last] - 1:
        result.append(last - j)
        last = j
    j -= 1

print(*reversed(result))

• Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] coins = {1, 2, 5, 10, 20, 50, 100};
        int INF = Integer.MAX_VALUE;
        
        int[] dp = new int[n + 1];
        Arrays.fill(dp, INF);
        dp[0] = 0;
        
        for (int val : coins) {
            for (int j = val; j <= n; j++) {
                dp[j] = Math.min(dp[j], dp[j - val] + 1);
            }
        }
        
        if (dp[n] == INF || n == 0) {
            System.out.println(-1);
            return;
        }
        
        List<Integer> result = new ArrayList<>();
        int last = n, j = n;
        while (j >= 0) {
            if (dp[j] == dp[last] - 1) {
                result.add(last - j);
                last = j;
            }
            j--;
        }
        
        Collections.reverse(result);
        for (int num : result) {
            System.out.print(num + " ");
        }
    }
}

• Cpp

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

const int INF = 0x3f3f3f3f;

int main() {
    int n;
    cin >> n;
    vector<int> coins = {1, 2, 5, 10, 20, 50, 100};
    
    vector<int> dp(n + 1, INF);
    dp[0] = 0;
    
    for (int val : coins) {
        for (int j = val; j <= n; j++) {
            dp[j] = min(dp[j], dp[j - val] + 1);
        }
    }
    
    if (dp[n] == INF || n == 0) {
        cout << -1 << endl;
        return 0;
    }
    
    vector<int> result;
    int last = n, j = n;
    while (j >= 0) {
        if (dp[j] == dp[last] - 1) {
            result.push_back(last - j);
            last = j;
        }
        j--;
    }
    
    reverse(result.begin(), result.end());
    for (int num : result) {
        cout << num << " ";
    }
    
    return 0;
}

🗳 02.单词拆分问题

问题描述

LYA最近在学习一门新的外语，他发现有些外来词在词典中并没有收录。为了方便学习和记忆，他想将这些生词拆分成词典中已有的单词。

现在给定一个词典，其中每个单词都有一个正整数权重。对于一个待拆分的单词，可以将其拆分成词典中出现的单词，且拆分得到的单词序列的权重之和最大。

例如，词典中有 、、 三个单词，权重分别为 、、。对于单词 ，可以拆分成 或 ，对应的权重之和分别为 和 ，因此应该拆分为 。

假设词典中最多有 个单词，每个单词的长度不超过 个字符。请你帮助LYA设计一个程序，能够根据词典将输入的单词拆分成权重之和最大的形式。

输入格式

第一行包含整数 ，表示词典中单词的个数。

接下来 行，每行包含一个单词和对应的权重值，以空格分隔。

最后一行输入一个待拆分的单词。

输出格式

如果可以将输入的单词拆分，则输出拆分后的结果，单词之间用 隔开。如果无法拆分，则原样输出待拆分的单词。

样例输入

7
ba 1
cef 2
cefs 3
s 2
dok 6
sdok 9
ok 3
bacefsdok

样例输出

/ba/cef/sdok

数据范围

单词长度

题解

本题可以使用动态规划来解决。设 表示将前 个字符拆分得到的最大权重和， 表示前 个字符拆分得到最大权重和时，最后一个单词的前一个字符的下标。

我们可以从前往后枚举每个字符作为当前拆分的结束位置，然后枚举上一个单词的结束位置，判断中间这一段是否能在词典中找到。如果能找到，就更新 和 。

最后，如果 的值没有被更新过，说明无法拆分，原样输出单词。否则，从 开始，依次向前跳转，就能得到拆分的单词序列。

参考代码

• Python

def main():
    n = int(input())
    words = {}
    for _ in range(n):
        word, weight = input().split()
        words[word] = int(weight)

    s = input()
    m = len(s)
    dp = [-float('inf')] * (m + 1)
    fore = [-1] * (m + 1)
    dp[0] = 0

    for i in range(1, m + 1):
        for j in range(i):
            word = s[j:i]