 # Dynamic Programming Implementation in Python

I am trying to solve this Problem.

I have a Python code and I need to fill in this one gap

# return an integer

def groceryShops(A, k):
if not A:
return 0

``````n = len(A) # n is the number of city centers.

if k >= n: # we should not have more shops than city centers.
return 0

A.sort()
cost = [[0 for _ in range(n + 1)] for _ in range(n + 1)]

"""
cost[i][j] is the minimum cost to build a shop between city centers i and j
This shop should be in the median of the city centers.
"""
for i in range(n):
for j in range(i, n):
mid = int(i + (j - i) / 2)
print("i= ", i, " j= ", j, "Median is: ", mid, " Center:",  A[mid], "\n")

for r in range(i, mid + 1):
cost[i + 1][j + 1] += A[mid] - A[r]
print("dist of ", A[mid] ," --to-> " ,  A[r], " Right ", cost[i + 1][j + 1])
for r in range(mid + 1, j + 1):
cost[i + 1][j + 1] += A[r] - A[mid]
print("dist of ",  A[mid] ," <--to-- " ,  A[r], " Left ", cost[i + 1][j + 1])
print("COST: ", "(", A[i ], "," ,A[j], " )", cost[i + 1][j + 1], "\n\n")

# print("cost")
# for row in cost:
#   for c in row:
#     print(c, end = " ")
#   print()
"""
dp[i][j] is the minimum cost for the first j city centers with i shops.
"""
dp = [[float('inf') for _ in range(n + 1)] for _ in range(k + 1)]
dp = 0

for i in range(1, k + 1):
for j in range(1, n + 1):
for r in range(j):
dp[i][j] =  ?? # only fill this gap :), min or max of some values using i, j and r?

# print("\n\nDP Table")
# for row in dp:
#   for c in row:
#     print(c, end = "       ")
#   print("\n")

return dp[-1][-1]
``````

Any help would be greatly appreciated