첫 번째 풀이 (시간 초과)

dp[x][y]: x에서 y로 가는 $K$의 최솟값
solve(x, y): dp[x][y]를 구하는 함수. 재귀로 구현
0->4만 구하면 되는데 모든 경우를 구하다 보니 재귀가 지나치게 많아져서 시간초과인 것으로 생각된다.

두 번째 풀이 (정답)

dp[x]: x에서 N-1까지 가는 $K$의 최솟값
solve(x): dp[x]를 구하는 함수. 재귀로 구현

코드

import sys
#sys.stdin = open('input.txt', 'r')
sys.setrecursionlimit(int(1e5))
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
dp = [-1 for _ in range(N)]


def solve(start):
    # 시작과 목표가 같으면 0
    if start == N - 1:
        dp[start] = 0
        return 0

	# 이미 계산한 거리라면 바로 리턴
    if dp[start] != -1:
        return dp[start]

	# 리턴값
    ret = float('inf')
    # start -> i -> (N - 1)
    for i in range(start + 1, N):
        cost = (i - start) * (1 + abs(A[start] - A[i]))
        tmp = max(cost, solve(i)) # 최대 힘(K)
        ret = min(ret, tmp) # K의 최솟값
    dp[start] = ret
    return dp[start]

answer = solve(0)
print(answer)