An even number of trees are left along one side of a country road. You've been assigned the job to plant these trees at an even interval on both sides of the road. The length and width of the road are variable, and a pair of trees must be planted at the beginning at 0 and at the end at length of the road. Only one tree can be moved at a time. The goal is to calculate the lowest amount of distance that the trees have to be moved before they are all in a valid position. Returns the minimum distance that trees have to be moved before they are all in a valid state. Parameters: tree listint: A sorted list of integers with all trees' position along the road. length int: An integer with the length of the road. width int: An integer with the width of the road. Returns: A float number with the total distance trees have been moved.
from math import sqrt

def planting_trees(trees, length, width):
    """
    Returns the minimum distance that trees have to be moved before they
    are all in a valid state.

        Parameters:
            tree (list<int>): A sorted list of integers with all trees'
                              position along the road.
            length (int): An integer with the length of the road.
            width (int): An integer with the width of the road.

        Returns:
            A float number with the total distance trees have been moved.
    """
    trees = [0] + trees

    n_pairs = int(len(trees)/2)

    space_between_pairs = length/(n_pairs-1)

    target_locations = [location*space_between_pairs for location in range(n_pairs)]

    cmatrix = [[0 for _ in range(n_pairs+1)] for _ in range(n_pairs+1)]
    for r_i in range(1, n_pairs+1):
        cmatrix[r_i][0] = cmatrix[r_i-1][0] + sqrt(
                width + abs(trees[r_i]-target_locations[r_i-1])**2)
    for l_i in range(1, n_pairs+1):
        cmatrix[0][l_i] = cmatrix[0][l_i-1] + abs(trees[l_i]-target_locations[l_i-1])

    for r_i in range(1, n_pairs+1):
        for l_i in range(1, n_pairs+1):
            cmatrix[r_i][l_i] = min(
                cmatrix[r_i-1][l_i] + sqrt(width + (trees[l_i + r_i]-target_locations[r_i-1])**2),
                cmatrix[r_i][l_i-1] + abs(trees[l_i + r_i]-target_locations[l_i-1])
            )

    return cmatrix[n_pairs][n_pairs]
