Сложная задача динамического программирования
spinner.setOnItemSelectedListener(
new AdapterView.OnItemSelectedListener() {
@Override
public void onItemSelected(AdapterView<?> arg0, View arg1,
int arg2, long arg3) {
// TODO Auto-generated method stub
}
@Override
public void onNothingSelected(AdapterView<?> arg0) {
// TODO Auto-generated method stub
}
//add some code here
}
);
1 ответ
Я создаю вклад, основанный на вкладе в дискуссию Дейва Аарона Смита.
Давайте пока не будем рассматривать последние два ограничения ((i,j) и (k,l)).
Только с одним столбцом (nx1) решение является q * (q - 1) ^ (n - 1).
Сколько вариантов для второго столбца?
(q-1) для верхней ячейки (1,2), но затем q-1 или q-2 для ячейки (2,2), если (1,2) / (2,1) имеют или не имеют одинаковый цвет. То же самое для (3,2): q-1 или q-2 решений.
Мы можем видеть, что у нас есть двоичное дерево возможностей, и нам нужно суммировать по этому дереву. Давайте предположим, что левый потомок всегда «одинакового цвета сверху и слева», а правый потомок «разных цветов».
Посредством вычисления по дереву числа возможностей для левого столбца для создания таких конфигураций и количества возможностей для новых ячеек, которые мы окрашиваем, мы посчитали бы количество возможностей для окрашивания двух столбцов.
Но давайте теперь рассмотрим распределение вероятностей для раскраски второго столбца: если мы хотим повторить процесс, нам нужно иметь равномерное распределение во втором столбце, это было бы так, как если бы первое никогда не существовало, и среди всех Окрашивая первые два столбца, можно сказать, что такие вещи, как 1/q, имеют цвет 0 в верхней ячейке второго столбца.
Без равномерного распределения это было бы невозможно.
Проблема: равномерно ли распределение?
Ответ: Мы бы получили то же число решений, построив сначала во втором столбце первый, а затем третий. Распределение второго столбца в этом случае является равномерным, поэтому оно также имеет место в первом случае.
Теперь мы можем применить ту же «идею дерева», чтобы подсчитать количество возможностей для третьего столбца.
Я попытаюсь развить это и построить общую формулу (поскольку дерево имеет размер 2 ^ n, мы не хотим его подробно исследовать).