2253: 蓝桥杯算法提高-和谐宿舍2

解题思路:
动态规划

注意事项:

为了推导dp时的下标遍历更简洁，输入数组首位添0；
因此应该注意倒数第二行的height的左右端点取值

参考代码:

import math
n, m = map(int, input().split())
height = [0] + list(map(int, input().split()))[:n]
dp = [[math.inf for _ in range(n + 1)] for _ in range(m + 1)]

for x in range(1, n + 1):
    dp[1][x] = max(height[:x + 1]) * x

for i in range(2, m + 1):  # woods
    for j in range(i, n + 1):
        for k in range(i, j):
            dp[i][j] = min(dp[i][j],
                           dp[i - 1][k] + max(height[k + 1:j + 1]) * (j - k))
print(dp[-1][-1])