一、编程题
1、最佳路径
如下所示的由正整数数字构成的三角形:
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，和最大的路径称为最佳路径。你的任务就是求出最佳路径上的数字之和。
注意：路径上的每一步只能从一个数走到下一层上和它最近的下边（正下方）的数或者右边（右下方）的数。
时间限制：1000
内存限制：65536
输入
第一行为三角形高度100>=h>=1，同时也是最底层边的数字的数目。 从第二行开始，每行为三角形相应行的数字，中间用空格分隔。
输出
最佳路径的长度数值。
样例输入
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
样例输出
30
提示
如何采用动态规划的思想，对问题进行分解。
参考答案：
无
解析：【喵呜刷题小喵解析】本题可以使用动态规划来解决。首先，我们定义一个二维数组dp，其中dp[i][j]表示从三角形的顶部到第i行第j个数字的路径上的最大和。然后，我们遍历三角形的每一行，对于每个数字，我们有两种选择：1. 从上一行的左边走到当前数字，即dp[i-1][j-1] + triangle[i][j]2. 从上一行的右边走到当前数字，即dp[i-1][j] + triangle[i][j]我们选择两种选择中的最大值作为dp[i][j]的值。最后，返回dp[n-1][n-1]，其中n为三角形的高度，即为最佳路径上的数字之和。在Python中，我们可以使用以下代码实现：```pythondef max_path_sum(triangle):n = len(triangle)dp = [[0] * (n + 1) for _ in range(n)]for i in range(n):for j in range(i + 1):if j == 0:dp[i][j] = triangle[i][j]else:dp[i][j] = triangle[i][j] + max(dp[i - 1][j - 1], dp[i - 1][j])return dp[n - 1][n - 1]n = int(input())triangle = []for _ in range(n):triangle.append(list(map(int, input().split())))print(max_path_sum(triangle))```其中，我们首先将输入的三角形存储在一个二维列表中，然后使用动态规划计算出最佳路径上的数字之和。最后，输出计算的结果即可。
2、邮票收集
小A是个邮票收集爱好家，他有n种面值的邮票，每种邮票都有无数张。一天小B想要寄信，需要一共面值和为k的邮票组合。小A想要知道拼出面值为k的邮票最少需要多少张。
时间限制：1000
内存限制：131072
输入
输入是多组数据。(不超过10组) 每组数据的第一行正整数n，k，表示邮票的种类数目和目标要拼出的钱。(0 < n ≤ 100, 0 < k ≤ 1000 ) 接下来的一行有n个正整数ai(0 < ai ≤ 1000)。 若n=k=0表示输入结束。
输出
每组数据输出一行一个数，分别表示拼出k需要的最少的邮票数量。 如果不存在能够拼出k的方案，输出-1。
样例输入
4 10
1 2 3 4
5 16
1 2 3 4 5
2 7
4 5
0 0
样例输出
3
4
-1
提示
第一组数据: 10 = 4+4+2 第二组数据：16 = 5+5+5+1 第三组数据： 不存在。
参考答案：
无
解析：【喵呜刷题小喵解析】：本题是一道典型的动态规划问题，可以使用动态规划算法来解决。首先，定义一个dp数组，dp[i]表示组成面值i的最小邮票数，初始值都设为无穷大，表示不可达。然后，遍历每一种面值的邮票，对于每种邮票，都尝试用它组成从该面值到k的所有面值，并更新dp数组。最后，如果dp[k]仍然是无穷大，表示无法组成面值k的邮票，输出-1；否则，输出dp[k]。本题的时间复杂度为O(n^2k)，其中n为邮票的种类数，k为目标面值。由于k的最大值为1000，因此本题的时间复杂度可以接受。
3、切割回文
阿福最近对回文串产生了非常浓厚的兴趣。
如果一个字符串从左往右看和从右往左看完全相同的话，那么就认为这个串是一个回文串。例如，"abcaacba"是一个回文串，"abcaaba"则不是一个回文串。
阿福现在强迫症发作，看到什么字符串都想要把它变成回文的。阿福可以通过切割字符串，使得切割完之后得到的子串都是回文的。
现在阿福想知道他最少切割多少次就可以达到目的。例如，对于字符串"abaacca"，最少切割一次，就可以得到"aba"和"acca"这两个回文子串。
时间限制：1000
内存限制：65536
输入
输入的第一行是一个整数 T (T <= 20) ，表示一共有 T 组数据。 接下来的 T 行，每一行都包含了一个长度不超过的 1000 的字符串，且字符串只包含了小写字母。
输出
对于每组数据，输出一行。该行包含一个整数，表示阿福最少切割的次数，使得切割完得到的子串都是回文的。
样例输入
3
abaacca
abcd
abcba
样例输出
1
3
0
提示
对于第一组样例，阿福最少切割 1 次，将原串切割为"aba"和"acca"两个回文子串。 对于第二组样例，阿福最少切割 3 次，将原串切割为"a"、“b”、“c”、"d"这四个回文子串。 对于第三组样例，阿福不需要切割，原串本身就是一个回文串。
参考答案：
无
解析：【喵呜刷题小喵解析】：对于这个问题，我们可以使用贪心算法来解决。我们从字符串的第二个字符开始遍历，检查从当前位置到字符串末尾的子串是否是回文串。如果是，说明我们可以在这个位置切割一次，然后得到两个回文子串。我们记录切割的次数，最后输出即可。这个算法的时间复杂度是O(n^2)，其中n是字符串的长度。对于输入规模，这个算法是可以接受的。对于样例输入：```3abaaccaabcdabcba```对于第一个字符串"abaacca"，我们可以切割一次，得到"aba"和"acca"两个回文子串，所以输出1。对于第二个字符串"abcd"，我们需要切割三次，得到"a"、"b"、"c"、"d"四个回文子串，所以输出3。对于第三个字符串"abcba"，它本身就是一个回文串，所以不需要切割，输出0。
4、小球放盒子
有N个相同的球，M个不同的盒子，每个盒子最多放K个球
请计算将这N个球全部放入盒子中的方案数模1000007后的结果
时间限制：10000
内存限制：131072
输入
三个正整数，依次为N，M，K
输出
输出方案数模1000007后的结果
样例输入
4 2 3
样例输出
3
提示
总共有3种方案，依次为 { 3 ， 1 }，{ 2 ， 2 }，{ 1 ， 3 }。 对于100%的数据， N，M ≤ 5000
参考答案：
无
解析：【喵呜刷题小喵解析】这个问题是一个经典的组合问题，可以使用动态规划来解决。动态规划的核心思想是将一个大问题分解成多个小问题，通过解决这些小问题来求解大问题。首先，我们需要定义一个二维数组 dp[i][j]，其中 dp[i][j] 表示将 i 个球放入 j 个盒子中的方案数。dp[i][j] 的值可以通过前面的子问题计算得出，即 dp[i][j] = dp[i-1][j-k] + dp[i-1][j-k+1] + ... + dp[i-1][j]，其中 k 的取值范围为 [1, min(j, i)]。具体来说，对于 dp[i][j]，我们需要遍历 k 的取值范围，计算 dp[i-1][j-k] 的值，并将其累加到 dp[i][j] 中。由于方案数可能会很大，我们需要对结果取模，以避免溢出。最后，我们只需要计算 dp[N][M] 的值即可，这就是将 N 个球放入 M 个盒子中的方案数。注意，由于 N 和 M 的取值范围很大，我们需要在计算 dp[i][j] 的值之前，将 dp[i][j] 的值初始化为 -1，以避免重复计算。当需要计算 dp[i][j] 的值时，如果 dp[i][j] 的值已经计算过，则直接返回之前的值。如果 dp[i][j] 的值还没有计算过，则计算其值，并将其保存在 dp[i][j] 中。
喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！
