题目:
代码:
# 分割数字串以最大化乘积的问题
def max_product(s, N, K):
# 动态规划数组,dp[i][j] 表示用j个乘号将前i个数字分割后得到的最大乘积
dp = [[0 for _ in range(K + 1)] for _ in range(N + 1)]
# 初始化dp数组,没有使用乘号时候的情况
# 这里初始化 dp[i][0],意味着没有使用任何乘号的情况。此时,最大乘积就是数字串的前 i 个数字直接组成的数。
for i in range(1, N + 1):
dp[i][0] = int(s[:i]) # 将前i个数字转换为整数
# 核心部分,用于计算所有状态。
# 外两层循环遍历所有的数字和乘号的可能组合。
for i in range(1, N + 1):
for j in range(1, K + 1):
# 遍历最后一个乘号可能的位置
for k in range(j - 1, i):
# num = int(s[k:i]) 计算从第 k+1 到第 i 个数字形成的数。
num = int(s[k:i])
# dp[i][j] = max(dp[i][j], dp[k][j - 1] * num) 更新状态,即在考虑最后一个乘号放在不同位置的所有情况下,选择能得到最大乘积的那个。
dp[i][j] = max(dp[i][j], dp[k][j - 1] * num)
return dp[N][K]
# 之后都这样写
N, K = map(int, input().split())
s = input()
print(max_product(s, N, K))