Упражнение с кластером чисел на Python

Question

Я выполняю упражнение в своем учебнике (пример 4.7) и реализую код на Python для практики динамического программирования.У меня возникли проблемы с выполнением алгоритма 4.8.Я понимаю, что происходит, пока не доберусь до 'В противном случае диапазон s от 1 до t-1 и установите s, чтобы минимизировать f(s).Почему книга использует s в цикле for, а также устанавливает для нее функцию f(s)?Как следует реализовать эту строку в Python?

[текущий код внизу]

Мой текущий код таков:

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)

Любая помощь очень ценится!

Answer 1

Алгоритм очень хорош. Мой код выглядит следующим образом.

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])

Совет: Если вы не понимаете алгоритм, вы можете запустить его вручную на бумаге, возможно, вы поймете, как он работает.