С динамическим программированием можно делать все что угодно - если вы готовы принять непрактично большое пространство состояний. В вашем случае, предположим, мы работаем в столбцах слева направо. На шаге k мы собираемся подсчитать количество различных способов заполнения первых k столбцов матрицы столбцами, содержащими n / 2 0 и n / 2 1, и мы знаем, для каждого отдельного состояния, число различных способы заполнения первых k-1 столбцов матрицы.
Что представляет собой государство? Нам нужно, чтобы он был достаточно подробным, чтобы, когда мы закончили, мы знали, что каждая строка содержит n / 2 0 и n / 2 1. Лучшее, о чем я думаю, это то, что штат сообщает нам, для каждого возможного i, количество строк, которые получили i 1s. Таким образом, на полпути через матрицу 4x4 наше состояние может сказать нам, что 2 строки имеют 2 1, а 2 строки имеют 0 1, или, для другого состояния, что все 4 строки получили один 1. В конце мы рассматриваем только число, связанное с состоянием, которое говорит нам, что каждая строка действительно получала ровно n / 2 1 с.
В нашем примере 4x4, при k = 1, есть только одно возможное состояние: 2 строки получили один 1, а две строки получили один 0. Мы могли бы использовать поиск в обратном порядке, чтобы определить возможные состояния преемника - 2 строки с 2 1 с и 2 строки с 0 1 с, 1 строка с 2 1 с, две строки с одинаковыми разбиениями и 1 строка без 1 с, или 4 строки с одинаковыми разбиениями. Учитывая это, мы можем определить количество частичных матриц, принадлежащих каждому состоянию.
Это решение для динамического программирования, но число различных частичных отсчетов в середине разработки большой матрицы само по себе будет большим, и вы можете видеть, что программирование нетривиально. Интересно, есть ли лучший способ сделать это?