Problem p03161 (python)

Fixed submission:
import math
from functools import lru_cache
def Frog1():
    n = int(input())
    h = list(map(int,input().split(' ')))
    @lru_cache(None)
    def Solve(i):
        if i==n-1:
            return 0
        if i==n-2:
            return abs(h[i]-h[i+1])
        return min(Solve(i+1)+abs(h[i]-h[i+1]),Solve(i+2)+abs(h[i]-h[i+2]))
    dp = [0]*n
    for i in reversed(range(n)):
        if i==n-1:
            dp[i] = 0
        elif i==n-2:
            dp[i] = abs(h[i]-h[i+1])
        else:
            dp[i] = min(dp[i+1]+abs(h[i]-h[i+1]),dp[i+2]+abs(h[i]-h[i+2]))
    print(dp[0])
def Frog2():
    n,k = input().split(' ')
    n,k = int(n),int(k)
    h = list(map(int, input().split(' ')))
    @lru_cache(None)
    def Solve(i):
        if i==n-1:
            return 0
        ans = math.inf
        for j in range(1,k+1):
            new_i = i+j
            if new_i<=n-1:
                ans = min(ans , Solve(new_i)+abs(h[i]-h[new_i]))
            else:
                break
        return ans

    dp = [0]*n
    for i in reversed(range(n)):
        if i==n-1:
            dp[i] = 0
        else:
            ans = math.inf
            for j in range(1,k+1):
                new_i = i+j
                if new_i<=n-1:
                    ans = min(ans,dp[new_i]+abs(h[i]-h[new_i]))
                else:
                    break
            dp[i] = ans
    print(dp[0])

Frog2()

Buggy submission (verdict: Runtime Error):
import math
class Graph(object):
    def __init__(self,v):
        self.v = v
        self.visited = [False for i in range(v)]
        self.adj = [[] for i in range(v)]
        self.parent = [-1 for i in range(v)]
        self.distance = [0 for i in range(v)]

    def AddEdge(self,a,b):
        self.adj[a].append(b)
        self.adj[b].append(a)

    def BFS(self,start):
        Q = [start]
        self.visited[start] = True
        while len(Q)>0:

            cur = Q.pop(0)
            for child in self.adj[cur]:
                if self.visited[child]==False:
                    self.visited[child] = True
                    self.distance[child] = self.distance[cur]+1
                    self.parent[child] = cur
                    Q.append(child)

    def CycleDetection_Using_BFS(self,start):
        Q = [start]
        self.visited[start] = True
        while len(Q)>0:

            cur = Q.pop(0)
            for child in self.adj[cur]:
                if self.visited[child]==False:
                    self.visited[child] = True
                    self.distance[child] = self.distance[cur]+1
                    self.parent[child] = cur
                    Q.append(child)
                else:
                    if self.parent[cur]!=child:
                        return True

        return False

NK= list(map(int,input().split(' ')))
n,k = NK[0] , NK[1]
h = list(map(int,input().split(' ')))
dp = [0]*n
for i in reversed(range(n)):
    m=math.inf
    if i==n-1:
        dp[i] = 0
    else:
        for j in range(1,k+1):
            Move = i+j
            if Move<=n-1:
                m = min(m,dp[Move]+abs(h[i]-h[Move]))
        dp[i] = 0 if m==math.inf else m
print(dp[0])

Buggy submission (verdict: Runtime Error):
import math
class Graph(object):
    def __init__(self,v):
        self.v = v
        self.visited = [False for i in range(v)]
        self.adj = [[] for i in range(v)]
        self.parent = [-1 for i in range(v)]
        self.distance = [0 for i in range(v)]

    def AddEdge(self,a,b):
        self.adj[a].append(b)
        self.adj[b].append(a)

    def BFS(self,start):
        Q = [start]
        self.visited[start] = True
        while len(Q)>0:

            cur = Q.pop(0)
            for child in self.adj[cur]:
                if self.visited[child]==False:
                    self.visited[child] = True
                    self.distance[child] = self.distance[cur]+1
                    self.parent[child] = cur
                    Q.append(child)

    def CycleDetection_Using_BFS(self,start):
        Q = [start]
        self.visited[start] = True
        while len(Q)>0:

            cur = Q.pop(0)
            for child in self.adj[cur]:
                if self.visited[child]==False:
                    self.visited[child] = True
                    self.distance[child] = self.distance[cur]+1
                    self.parent[child] = cur
                    Q.append(child)
                else:
                    if self.parent[cur]!=child:
                        return True

        return False

NK= list(map(int,input().split(' ')))
n,k = NK[0] , NK[1]
h = list(map(int,input().split(' ')))
dp = [0]*n
for i in reversed(range(n)):
    m=math.inf
    for j in range(1,k+1):
        Move = i+j
        if Move<=n-1:
            m = min(m,dp[Move]+abs(h[i]-h[Move]))
    dp[i] = 0 if m==math.inf else m
print(dp[0])

Buggy submission (verdict: Runtime Error):
import math
class Graph(object):
    def __init__(self,v):
        self.v = v
        self.visited = [False for i in range(v)]
        self.adj = [[] for i in range(v)]
        self.parent = [-1 for i in range(v)]
        self.distance = [0 for i in range(v)]

    def AddEdge(self,a,b):
        self.adj[a].append(b)
        self.adj[b].append(a)

    def BFS(self,start):
        Q = [start]
        self.visited[start] = True
        while len(Q)>0:

            cur = Q.pop(0)
            for child in self.adj[cur]:
                if self.visited[child]==False:
                    self.visited[child] = True
                    self.distance[child] = self.distance[cur]+1
                    self.parent[child] = cur
                    Q.append(child)

    def CycleDetection_Using_BFS(self,start):
        Q = [start]
        self.visited[start] = True
        while len(Q)>0:

            cur = Q.pop(0)
            for child in self.adj[cur]:
                if self.visited[child]==False:
                    self.visited[child] = True
                    self.distance[child] = self.distance[cur]+1
                    self.parent[child] = cur
                    Q.append(child)
                else:
                    if self.parent[cur]!=child:
                        return True

        return False

NK= list(map(int,input().split(' ')))
n,k = NK[0] , NK[1]
h = list(map(int,input().split(' ')))
dp = [math.inf]*n
for i in reversed(range(n)):
    m = math.inf
    for j in range(1,k+1):
        Move = i+j
        if Move<=n-1:
            m = min(m,dp[Move]+abs(h[i]-h[Move]))
    dp[i] = m if m!=math.inf else 0
print(dp[0])

Buggy submission (verdict: Runtime Error):
NK= list(map(int,input().split(' ')))
n,k = NK[0] , NK[1]
h = list(map(int,input().split(' ')))
''''
dp = {}
def Frog2(i):
   if i==n-1:
       return 0
   if i in dp:
       return dp[i]
   m = math.inf
   for j in range(1,k+1):
       if i+j<=n-1:
           m = min(m,Frog2(j+i)+abs(h[i]-h[j+i]))
   dp[i] = m
   return dp[i]
print(Frog2(0))
'''
dp = [0]*n
for i in reversed(range(n)):
    m = math.inf
    for j in range(1,k+1):
        Move = i+j
        if Move<=n-1:
            m = min(m,dp[Move]+abs(h[i]-h[Move]))
    dp[i] = m if m!=math.inf else dp[i]
print(dp[0])

Buggy submission (verdict: Runtime Error):
import math
class Graph(object):
    def __init__(self,v):
        self.v = v
        self.visited = [False for i in range(v)]
        self.adj = [[] for i in range(v)]
        self.parent = [-1 for i in range(v)]
        self.distance = [0 for i in range(v)]

    def AddEdge(self,a,b):
        self.adj[a].append(b)
        self.adj[b].append(a)

    def BFS(self,start):
        Q = [start]
        self.visited[start] = True
        while len(Q)>0:

            cur = Q.pop(0)
            for child in self.adj[cur]:
                if self.visited[child]==False:
                    self.visited[child] = True
                    self.distance[child] = self.distance[cur]+1
                    self.parent[child] = cur
                    Q.append(child)

    def CycleDetection_Using_BFS(self,start):
        Q = [start]
        self.visited[start] = True
        while len(Q)>0:

            cur = Q.pop(0)
            for child in self.adj[cur]:
                if self.visited[child]==False:
                    self.visited[child] = True
                    self.distance[child] = self.distance[cur]+1
                    self.parent[child] = cur
                    Q.append(child)
                else:
                    if self.parent[cur]!=child:
                        return True

        return False

NK= list(map(int,input().split(' ')))
n,k = NK[0] , NK[1]
h = list(map(int,input().split(' ')))

dp = {}
def Frog2(i):
   if i==n-1:
       return 0
   if i in dp:
       return dp[i]
   m = math.inf
   for j in range(1,k+1):
       if i+j<=n-1:
           m = min(m,Frog2(j+i)+abs(h[i]-h[j+i]))
   dp[i] = m
   return dp[i]
print(Frog2(0))

Buggy submission (verdict: Runtime Error):
import math
class Graph(object):
    def __init__(self,v):
        self.v = v
        self.visited = [False for i in range(v)]
        self.adj = [[] for i in range(v)]
        self.parent = [-1 for i in range(v)]
        self.distance = [0 for i in range(v)]

    def AddEdge(self,a,b):
        self.adj[a].append(b)
        self.adj[b].append(a)

    def BFS(self,start):
        Q = [start]
        self.visited[start] = True
        while len(Q)>0:

            cur = Q.pop(0)
            for child in self.adj[cur]:
                if self.visited[child]==False:
                    self.visited[child] = True
                    self.distance[child] = self.distance[cur]+1
                    self.parent[child] = cur
                    Q.append(child)

    def CycleDetection_Using_BFS(self,start):
        Q = [start]
        self.visited[start] = True
        while len(Q)>0:

            cur = Q.pop(0)
            for child in self.adj[cur]:
                if self.visited[child]==False:
                    self.visited[child] = True
                    self.distance[child] = self.distance[cur]+1
                    self.parent[child] = cur
                    Q.append(child)
                else:
                    if self.parent[cur]!=child:
                        return True

        return False

NK= list(map(int,input().split(' ')))
n,k = NK[0] , NK[1]
h = list(map(int,input().split(' ')))

dp = {}
def Frog2(i):
   if i==n-1:
       return 0
   if i in dp:
       return dp[i]
   m = math.inf
   for j in range(1,k+1):
       if i+j<=n-1:
           m = min(m,Frog2(j+i)+abs(h[i]-h[j+i]))
   dp[i] = m
   return dp[i]
print(Frog2(0))