最初のプール(タイムアウト)

dp[x][y]:xからyまでのKKの最大値solve(x, y):dp[x][y]の関数を求めます.再帰路実施
0->4を求めれば良いのですが、全てのケースを求めれば結果的に耳が多くなってタイムアウトだと思います.

2番目の答え(正しい)

dp[x]:xからN-1までのKKの最大値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)