2020网易：表达式求值[Python][动态规划]

简单问题，可以进行推广：其一，本题中只有三个数，因此直接枚举；其二，若有n个数，则是个dp问题。

# 3个数直接枚举
from functools import reduce
a, b, c = map(int, input().split())

all_plus = sum([a, b, c])
all_multi = reduce(lambda i,j: i*j, [a, b, c])

res = [all_plus, all_multi, a+b*c, a*b+c, (a+b)*c, a*(b+c)]
print(max(res))

写出其动态转移方程：

# 若有n个数，则是dp问题

nums = list(map(int, input().split()))
N = len(nums)
dp = [[nums[i] if i==j else 0 for j in range(N)] for i in range(N)] # dp[i][j] 第i个数到第j个数的最大
# 注意其初始化条件

for i in range(N):
    for j in range(i+1, N):
        for k in range(i, j): # 分段
            dp[i][j] = max([dp[i][k]+dp[k+1][j], dp[i][k]*dp[k+1][j], dp[i][j]]) # max(和， 积， 自身)

print(dp[0][N-1])