Minimum crosses over N parallel lines

Here is an draft-solution solving the problem using Brute force assuming an optimal solution for n bars can be found in a grid having n+1 columns only (This assumptions seems wrong at least for n>=8. By changing parameters the search can be extended, worst Case is sum(n-1, ... 1), but this will further slow down search, mostly by adding redundant solutions).

The algorithm has exponential complexity and will only give results within useful time for very low numbers. As I said in the comments, this approach can be somewhat improved by reducing the search space allowing only combinations of bars that have sandclock shape (long bars outside, short bars inside, the outermost bars are longest, cover the same space, and all other bars can be placed inside the outermost columns). However so far I found no other useful property to use. Note some property might exist that only is true for some optimal solutions, e.g. that the center bar has lenght 2.

A better way might be to use exactly sum(n-1, ... 1) columns, with each connection having it's own column, the number of variants might actually be lower.

Whether a useful dynamic programming solution exists, I don't know.

public class BarConnection {

    static class Bar {
        int start, end;
        private final int maxlength, minlength;

        Bar(int maxlength, int minlength) {
            this.maxlength = maxlength;
            this.minlength = minlength;
            reset();
        }

        public boolean next() {
            start++;
            if (start > 0) {
                return reset((end - start) + 2);
            }
            end++;
            return true;
        }

        public void reset() {
            reset(minlength);
        }

        public boolean reset(int length) {
            if (length > maxlength) {
                return false;
            }
            start = -length;
            end = 0;
            return true;
        }
    }

    static class Solution {
        private Bar[] bars;
        private int globalmin, globalmax, cost;

        Solution(int n) {
            bars = new Bar[n];
            for (int i = 0; i < n; i++) {
                bars[i] = new Bar(/* maxlength */ n, /* minlength */ 1);
            }
        }

        private boolean connect(final int maxcost) {
            cost = Integer.MAX_VALUE;
            int sumcost = 0;
            for (int i = 0; i < (bars.length - 1); i++) {
                for (int j = i + 1; j < bars.length; j++) {
                    final int pairCost = minCostBetween(i, j);
                    if (pairCost == 0) {
                        continue;
                    }
                    sumcost += pairCost;
                    if (sumcost > maxcost) {
                        return false;
                    }

                }
            }
            cost = sumcost;
            return true;
        }

        boolean nextSolution(final int maxcost) {
            while (true) {
                while (bars[0].next()) {
                    if (connect(maxcost)) {
                        return true;
                    }
                }
                bars[0].reset();
                for (int i = 1; i < bars.length; i++) {
                    if (bars[i].next()) {
                        break;
                    }
                    if (i == bars.length - 1) {
                        return false;
                    }
                    bars[i].reset();
                }
                if (connect(maxcost)) {
                    return true;
                }
            }
        }

        private int minCostBetween(final int i, final int j) {
            int minConnectionCost = -1;
            for (int k = Math.max(bars[i].start, bars[j].start); k <=
                    Math.min(bars[i].end, bars[j].end); k++) {
                // calculate cost for connecting at column k
                int newcost = 0;
                for (int l = i + 1; l < j; l++) {
                    final Bar midbar = bars[l];
                    if ((k >= midbar.start) && (k <= midbar.end)) {
                        newcost++;
                        if ((minConnectionCost >= 0) && (newcost >=
                                minConnectionCost)) {
                            break;
                        }
                    }
                }
                if ((minConnectionCost < 0) || (newcost < minConnectionCost)) {
                    minConnectionCost = newcost;
                    if (newcost == 0) {
                        break;
                    }
                }
            }
            return minConnectionCost;
        }
    }


    public static void main(String[] args) {
        int n = 6
        final Solution searchState = new Solution(n);
        int minCost = Integer.MAX_VALUE;
        while(true) {
            if (!searchState.nextSolution(minCost - 1)) {
                break;
            }
            minCost = searchState.cost, minCost;
            if (minCost == 0) {
                break;
            }
        }

        System.out.println("n=" + n + ", p=" + minCost);
    }
}