动态规划 | 乘积最大

2023-12-24 06:25:48

题目描述

原题链接

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

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

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

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

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

这时,符合题目要求的结果是: 31 × 2 = 62 31 \times 2 = 62 31×2=62

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

提示

数据范围与约定

对于 60 % 60\% 60% 的测试数据满足 6 ≤ N ≤ 20 6≤N≤20 6N20
对于所有测试数据, 6 ≤ N ≤ 40 , 1 ≤ K ≤ 6 6≤N≤40,1≤K≤6 6N40,1K6

问题分析

状态定义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 ≤ N ≤ 40 , 1 ≤ K ≤ 6 6≤N≤40,1≤K≤6 6N40,1K6。若用 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 ) O(KN^2) O(KN2)

文章来源:https://blog.csdn.net/qq_45931691/article/details/135177238
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。