Problem p03161 (python)

Fixed submission:
n, k = map(int, input().split())
h = list(map(int, input().split()))
dp = [0] * n

for i in range(n):
    if i == 0:
        dp[0] = 0
    elif i == 1:
        dp[1] = abs(h[0]-h[1])
    else:
        costs = []
        for j in range(1, k+1):
            if j > i:
                break
            if abs(h[i-j]-h[i]) == 0:
                costs.append(dp[i-j])
                break
            costs.append(dp[i-j] + abs(h[i-j]-h[i]))

        # if i == 3:
        #     print(costs)
        dp[i] = min(costs)

#print(dp)
print(dp[n-1])

Buggy submission (verdict: Runtime Error):
N, K = map(int, input().split())
h = list(map(int, input().split()))
dp = [None] * N

def solve(idx):
    if dp[idx] is not None:
        return dp[idx]

    if idx == N - 1:
        dp[idx] = 0
    elif idx == N - 2:
        dp[idx] = abs(h[idx] - h[idx + 1])
    else:
        temp = 10**10
        for k in range(1, K + 1):
            if idx + k == N:
                break
            temp = min(temp, solve(idx + k) + abs(h[idx] - h[idx + k]))
        dp[idx] = temp
    return dp[idx]

print(solve(0))

Buggy submission (verdict: Runtime Error):
N, K = map(int, input().split())
h = list(map(int, input().split()))
dp = [None] * N

def solve(n):
    if dp[n] is not None:
        return dp[n]

    if n == 0:
        dp[n] = 0
    elif n == 1:
        dp[n] = abs(h[0] - h[1])
    else:
        ans = 10**10
        for i in range(1, K+1):
            if n - i < 0:
                break
            if dp[n - i] is not None:
                temp = dp[n - i]
            else:
                temp = solve(n - i)
            ans = min(ans, temp + abs(h[n - i] - h[n]))
        dp[n] = ans

    return dp[n]

print(solve(N-1))

Buggy submission (verdict: Runtime Error):
n, k = map(int, input().split())
h = list(map(int, input().split()))
dp = [None] * n

def solve(idx):
    if idx == 0:
        return 0
    if idx == 1:
        return abs(h[0] - h[1])
    if dp[idx] is not None:
        return dp[idx]

    # dp[idx - 1] + abs(h[idx - 1] - h[idx])
    # dp[idx - 2] + abs(h[idx - 2] - h[idx])
    # ...
    # dp[idx - k] + abs(h[idx - k] - h[idx])

    ans = 10**10
    for i in range(1, k+1):
        if idx - i < 0:
            break
        prev = solve(idx - i)
        temp = prev + abs(h[idx - i] - h[idx])
        ans = min(ans, temp)

    dp[idx] = ans
    return ans

print(solve(n-1))

Buggy submission (verdict: Runtime Error):
n, k = map(int, input().split())                                         |n = int(input())
h = list(map(int, input().split()))                                      |h = list(map(int, input().split()))
dp = [0] * n                                                             |dp = [0]*n
                                                                         |
for i in range(n):                                                       |for i in range(n):
    if i == 0:                                                           |    if i == 0:
        dp[0] = 0                                                        |        dp[0] = 0
    elif i == 1:                                                         |    elif i == 1:
        dp[1] = abs(h[0]-h[1])                                           |        dp[1] = abs(h[0]-h[1])
    else:                                                                |    else:
        costs = []                                                       |        cost1 = dp[i-1] + abs(h[i-1]-h[i])
        for j in range(1, k+1):                                          |        cost2 = dp[i-2] + abs(h[i-2]-h[i])
            if j > i:                                                    |        dp[i] = min(cost1, cost2)
                break                                                    |
            if abs(h[i-j]-h[i]) == 0:                                    |print(dp[n-1])
                costs.append(dp[i-j])                                    |
                break                                                    |
            costs.append(dp[i-j] + abs(h[i-j]-h[i]))                     |
                                                                         |
        # if i == 3:                                                     |
        #     print(costs)                                               |
        dp[i] = min(costs)                                               |
                                                                         |
#print(dp)                                                               |
print(dp[n-1])                                                           |
                                                                         |