学不好python的小猫

学不好python的小猫

题目:

代码:

# 分割数字串以最大化乘积的问题
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))

 

11-11 14:10