Ufdjrw

I am working through an exercise in my textbook (Ex 4.7) and am implementing the code in Python to practice dynamic programming. I am having some trouble actually executing Algorithm 4.8. I understand what is going on until I get to 'Otherwise range s from 1 to t-1 and set s to minimize f(s). Why is the book using s in the for loop as well as setting it to the function f(s)? How should one go about implementing that line in Python?

[current code at bottom]

My current code is this so far:

x = [1,2,5,6,10]
k = 3
n = 5

r = [[0 for x in range(k)] for x in range(n)]
c = [[0 for x in range(k)] for x in range(n)]

def Union(lst1, lst2):
 final_list = lst1 + lst2
 return final_list

for j in range(k):
 for t in range(n):
 if j == 0:
 r[t][j] = (x[t]-x[0])/2
 c[t][j] = [(x[t]+x[0])/2]
 else:
 for s in range(t-1):
 f = max(r[s][j-1], (x[t]-x[s+1])/2)
 #set s to minimize f??
 r[t][j] = f
 w = []
 w.append((x[t]+x[s+1])/2)
 if c[s][j-1] == 0:
 c[t][j] = w
 else:
 c[t][j] = Union(c[s][j - 1], w)

print(r)
print(c)

Any help is much appreciated!

The algorithm is very good. My code is as follow.

x = [1,2,5,6,10]
k = 3
n = 5

r = [[[] for _ in range(k)] for _ in range(n)]
c = [[[] for _ in range(k)] for _ in range(n)]


def f(s, j_down, t):
 return max(r[s][j_down], (x[t]-x[s+1])/2.)

def get_min_f_and_s(j_down, t):
 """ range s from 1 to t-1 and set s to minimize f(s) 
 for example t=5 and j=3, so s range from 1 to 4, if f(1)=0.5, f(2)=0.4, f(3)=0.1, f(4)= 1.0, so f(4) is min one and s=2.
 And r[5][j] = f(2).
 """
 items = [(s, f(s, j_down, t))for s in range(t)]
 s, min_f = min(items, key=lambda x:x[1])
 return s, min_f

for j in range(k):
 if j == 0:
 for t in range(n):
 for t in range(n):
 r[t][j] = (x[t]-x[0])/2.0
 c[t][j] = [(x[t]+x[0])/2.0]
 else:
 for t in range(1, n):
 s, min_f = get_min_f_and_s(j-1, t)
 r[t][j] = min_f

 c[t][j] = c[s][j-1] + [(x[t]+x[s+1])/2.,]

print(r[-1][-1])
print(c[-1][-1])

A advice :
When don't understand algorithm, you can run it by hand in scratch paper, maybe you will figure out how it work.