动态规划 | 乘积最大

题目描述

原题链接

今年是国际数学联盟确定的“2000——世界数学年”，又恰逢我国著名数学家华罗庚先生诞辰 90 周年。在华罗庚先生的家乡江苏金坛，组织了一场别开生面的数学智力竞赛的活动，你的一个好朋友 XZ 也有幸得以参加。活动中，主持人给所有参加活动的选手出了这样一道题目：

设有一个长度为 $N$ 的数字串，要求选手使用 $K$ 个乘号将它分成 $K+1$ 个部分，找出一种分法，使得这 $K+1$ 个部分的乘积能够为最大。

同时，为了帮助选手能够正确理解题意，主持人还举了如下的一个例子：

有一个数字串：$312$，当 $N=3,K=1$ 时会有以下两种分法：

1. $3\times 12=36$
2. $31\times 2=62$

这时，符合题目要求的结果是：$31\times 2=62$。

现在，请你帮助你的好朋友 XZ 设计一个程序，求得正确的答案。

提示

数据范围与约定

对于 $60\%$ 的测试数据满足 $6\le N\le 20$。
对于所有测试数据，$6\le N\le 40,1\le K\le 6$。

问题分析

状态定义：dp[i][k]表示对于数字串s[0...i]，添加 k 个乘号，对应的乘积最大值。

有了上述的状态定义，我们可以发现，对于任意的dp[i][k]都可以由两部分组成，一部分是前 p 个数字串中包含 k - 1 个乘号，另一部分是剩下部分的数字串不包含乘号。然后遍历所有可能的分割点 p，找两部分乘积的最大值。

状态计算：

• dp[i][k] = max(dp[i][k], dp[p][k-1] * s[p + 1 ... n - 1])

边界情况：

• dp[i][0] = s[0...i]，即若不添加乘号，则数字串s[0...i]的乘积最大值为本身。

程序代码

由于对于所有测试数据，$6\le N\le 40,1\le K\le 6$。若用 C++ 实现，涉及大数乘法的问题，需要用到高精度的策略进行求解。这里为了重点突出算法思想，采用 Python 进行实现，避开高精度的问题。

n, k= map(int, input().split())
s = input()
dp = [[0 for i in range(k + 1)] for j in range(n)]
# 初始化
for i in range(n):
    dp[i][0] = int(s[0 : i + 1])
# 乘号个数
for i in range(1, k + 1):
    # s[0...j]
    for j in range(i + 1, n):
        # 考虑分界点
        for p in range(i - 1, j):
            dp[j][i] = max(dp[j][i], dp[p][i-1] * int(s[p + 1 : j + 1]))
print(dp[n-1][k])

复杂度分析

时间复杂度为 $O(K{N}^2)$