Buggy python submission (verdict: Time Limit Exceeded):
from functools import lru_cache

n, k = map(int, input().split())
h = [0] + list(map(int, input().split())) + [0]
INF = 10 ** 18


@lru_cache(maxsize=None)
def solve(i, nokori):
    if i == 0:
       return 0
    res = INF
    for j in range(nokori + 1):
        if i - 1 - j < 0:
            break
        diff = max(h[i] - h[i - 1 - j], 0)
        res = min(solve(i - 1 - j, nokori - j) + diff, res)
    return res


print(solve(n + 1, k))

Fixed submission:
n, k = map(int, input().split())
h = list(map(int, input().split()))
INF = 10**18

k = n - k

dp = [[INF]*(k+1) for i in range(n+1)]
dp[0][0] = 0

# i番目のブロックを必ず選ぶ
for i in range(n):
    # すでにj回選んでいる
    for j in range(k):
        if j == 0:
            dp[i+1][j+1] = min(dp[0][j] + h[i], dp[i+1][j+1])
            continue
        #最後に選んだブロックはlast_i番目
        for last_i in range(i):
            if last_i + 1 < j:
                continue
            dp[i+1][j+1] = min(dp[last_i+1][j] + max(h[i] - h[last_i], 0), dp[i+1][j+1])

ans = 10**18
for i in range(n+1):
    ans = min(dp[i][k], ans)

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from functools import lru_cache

n, k = map(int, input().split())
h = [0] + list(map(int, input().split())) + [0]
INF = 10 ** 18


@lru_cache(maxsize=10**9)
def solve(i, nokori):
    if i == 0:
       return 0
    res = INF
    for j in range(nokori + 1):
        if i - 1 - j < 0:
            break
        diff = max(h[i] - h[i - 1 - j], 0)
        res = min(solve(i - 1 - j, nokori - j) + diff, res)
    return res


print(solve(n + 1, k))

Fixed submission:
n, k = map(int, input().split())
h = list(map(int, input().split()))
INF = 10**18

k = n - k

dp = [[INF]*(k+1) for i in range(n+1)]
dp[0][0] = 0

# i番目のブロックを必ず選ぶ
for i in range(n):
    # すでにj回選んでいる
    for j in range(k):
        if j == 0:
            dp[i+1][j+1] = min(dp[0][j] + h[i], dp[i+1][j+1])
            continue
        #最後に選んだブロックはlast_i番目
        for last_i in range(i):
            if last_i + 1 < j:
                continue
            dp[i+1][j+1] = min(dp[last_i+1][j] + max(h[i] - h[last_i], 0), dp[i+1][j+1])

ans = 10**18
for i in range(n+1):
    ans = min(dp[i][k], ans)

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
h = [0] + list(map(int, input().split())) + [0]
INF = 10 ** 18

def solve(i, nokori):
    if i == 0:
       return 0
    res = INF
    for j in range(nokori + 1):
        if i - 1 - j < 0:
            break
        diff = max(h[i] - h[i - 1 - j], 0)
        res = min(solve(i - 1 - j, nokori - j) + diff, res)
    return res

print(solve(n + 1, k))

Fixed submission:
n, k = map(int, input().split())
h = list(map(int, input().split()))
INF = 10**18

k = n - k

dp = [[INF]*(k+1) for i in range(n+1)]
dp[0][0] = 0

# i番目のブロックを必ず選ぶ
for i in range(n):
    # すでにj回選んでいる
    for j in range(k):
        if j == 0:
            dp[i+1][j+1] = min(dp[0][j] + h[i], dp[i+1][j+1])
            continue
        #最後に選んだブロックはlast_i番目
        for last_i in range(i):
            if last_i + 1 < j:
                continue
            dp[i+1][j+1] = min(dp[last_i+1][j] + max(h[i] - h[last_i], 0), dp[i+1][j+1])

ans = 10**18
for i in range(n+1):
    ans = min(dp[i][k], ans)

print(ans)