最大乘法算式，本题是2022年3月13日举办的第13届蓝桥杯青少组Python编程选拔赛真题编程部分第5题。定一个正整数M和一个数字字符串，使用M个乘号插入到字符串中，请计算并输出最大乘积。
先来看看题目的要求吧。
编程实现：
给定一个正整数 M（1 ≤ M ≤ 5）和一个只包含数字的字符串（5 ＜ 字符串长度 ≤ 20）。使用M个乘号插入到字符串中，且两个乘号不能相邻，插入后生成一个乘法算式。找出一种使乘法算式数值最大的插入方式，并将结果输出。（乘号不能放在字符串的首尾位置）
如M = 2，字符串为123456，插入2个乘号。插入方式有：
1 * 2 * 3456 = 6912 ， 1 * 23 * 456 = 10488 ， 1 * 234 * 56 = 13104 ， 1 * 2345 * 6 = 14070 ，12 * 3 * 456 = 16416 ， 12 * 34 * 56 = 22848 ， 12 * 345 * 6 = 24840 ， 123 * 4 * 56 = 27552 ，123 * 45 * 6 = 33210，1234 * 5 * 6 = 37020，
其中乘法算式数值最大是第十种，为37020。
输入描述：
第一行输入一个正整数 M（1 ≤ M ≤ 5），表示乘号个数
第二行输入一个只包含数字的字符串（5 ＜ 字符串长度 ≤ 20），表示要插入M个乘号的字符串
输出描述：
输出一个整数，表示最大乘积数值
样例输入：sd2123456
样例输出：
这是一道经典的算法题，涉及的知识点包括循环、列表、字符串、枚举算法和动态规划等。
今年是国际数学联盟确定的“2000——世界数学年”，又恰逢我国著名数学家华罗庚先生诞辰 90 周年。在华罗庚先生的家乡江苏金坛，组织了一场别开生面的数学智力竞赛的活动，你的一个好朋友 XZ 也有幸得以参加。
活动中，主持人给所有参加活动的选手出了这样一道题目：设有一个长度为N的数字串，要求选手使用 K个乘号将它分成K + 1个部分，找出一种分法，使得这K+1个部分的乘积能够为最大。
枚举算法 递归算法 动态规划算法
combinations(range(5), 2)(0, 1), (0, 2), (0, 3), (0, 4),(1, 2), (1, 3), (1, 4),(2, 3), (2, 4),(3, 4)
1 * 2 * 3456 = 6912f(5, 1) * s[5: 6]f(4, 1) * s[4: 6]f(3, 1) * s[3 :6]f(2, 1) * s[2: 6]
for k in range(1, i):f(i, j) = max(f(i, j),f(k, j - 1) * int(s[k:i]))
定义DP数组 初始化DP数组 状态转移方程 遍历顺序
i <= j时，dp[i][j] = 0； j = 0时，dp[i][j] = int(s[:i])；
for k in range(1, i):dp(i, j) = max(dp(i, j),dp(k, j - 1) * int(s[k:i]))
dp[2][1]= max(dp[2][1], dp[1][1] * int(s[1:2]))= max(0, 1 * 2)= 2
dp[1][0] * int(s[1:3]) = 1 * 23 = 23dp[2][0] * int(s[2:3]) = 12 * 3 = 36
dp[1][0] * int(s[1:4]) = 1 * 234 = 234dp[2][0] * int(s[2:4]) = 12 * 34 = 408dp[3][0] * int(s[3:4]) = 12 * 34 = 492
思路有了，接下来，我们就进入具体的编程实现环节。
枚举算法
递归算法
动态规划
1. 枚举算法
根据前面的思路分析，我们使用combinations()函数获取所有组合，逐个计算乘积，从而获取最大值，代码如下：
代码比较长，说明4点：
1). 首先使用组合函数，获取所有组合，然后对字符串截取，将截取的数字串保存到临时列表temp中，如['1', '2', '3456']；
2). 为方便计算数字串的乘积，定义了一个f()函数，它将temp列表中的数字串依次取出，转成整型，累乘得到成绩，保存到res列表中；
3). res列表保存的是所有乘法算式的乘积，最后使用max()函数获取最大值并输出；
4). 在拆分字符串的时候，需要注意不断地更新和计算起点start和end，同时不要忘了最后一个乘号✖️后面的数字串。
2. 递归算法
使用带备忘录的递归算法，编写代码如下：
代码不算少，说明两点：
1). 为了方便，这里将备忘录列表作为递归的参数进行传递，真正的关键还是i和j这两个参数；
2). 在循环取值的时候，k是从1开始的，确保函数能满足结束条件；
2. 动态规划
根据前面的思路分析，使用动态规划算法，编写代码如下：
代码相对较少，强调两点：
1). 在遍历二维列表的时候，我们始终要遵循i表示行，j表示列的原则，如果要先遍历列，那就先写j，再嵌套i；
2). 对于每一列，起点是从 i + 1开始的，请参考填充DP表格的过程。
至此，整个程序就全部完成了，你可以输入不同的数据来测试效果啦。
循环语句；
列表操作；
枚举算法；
组合函数；
递归算法；
动态规划算法；
作为本次测评的最后一题，难度较大。关键点有两个，一是使用组合函数快速解决问题，二是使用递归思维深入分析计算最大乘积的过程，找到其中的规律，然后选择相应的算法编程实现。
对于本题而言，最基础的方法就是枚举算法，最高效的方法当属动态规划，而递归则是一种讨巧的实现方法。
枚举算法简单粗暴，如果一时半会找不到其他的解决方案，建议可以从枚举算法着手，先确保能解决问题或部分解决问题。
在使用枚举算法解决问题的过程中，说不定灵感就来了，想到更好的方法。实际上，大部分算法都是在枚举的基础上进行优化的。
很多同学都喜欢动态规划，从而忽略了递归算法，我倒是提倡大家多尝试使用递归思维来分析解决问题。
从本质上讲，动态规划和递归算法的核心是一样，但是递归算法的编写难度要小于动态规划，往往会给你带来意想不到的效果。
最后说说动态规划，动态规划的分析过程就是填充表格的过程，所以在解决动态规划问题时，一定要踏踏实实的逐步分析并填充表格，最终的代码往往是比较简单的。
你还有什么好的想法和创意吗，也非常欢迎和超平老师分享探讨。
需要源码的，可以添加本人微信。
另外，超平老师创建了一个蓝桥杯备考交流群，这是专门为老师和家长打造的免费社群，您可以与来自全国各地的老师、家长共同交流经验，分享学习心得。
超平老师也会给大家带来及时的赛事动态，备考攻略，真题资源分享，帮助各位更好地备考第15届蓝桥杯赛事，力争取得优异的成绩。
扫码或长按加入微信群
