Как будет выглядеть алгоритм?

Честно, не эксперт в питоне.

Что-то вроде этого должно работать:

dp=[[None, None]] * n
take = [[0,0]] * n

Потом можно общаться к dp[i][j]. Массив a можно сделать глобальным, или просто передавать в функцию - это копий лишних делать не будет.

Как будет выглядеть алгоритм?

Рекурсию я использовал потому что так оно проще понимается. Про то, что это же решение можно сделать циклом, я тоже написал, вы на эту фразу ответили весьма агрессивно - мол это позор и костыль.

Как будет выглядеть алгоритм?

> А вот это - реально костыль и позор. Я как-то обошелся, не самым производительным способом (можно было бы не считать на каждом шагу сумму, код бы вышел длиннее), но без позорных костылей.

Что простите?! Чем это ДП снизу-вверх это костыль и позор? Сокращение памяти до O(1) - это в чем позор-то? Вы именно так, видимо, почти и сделали, только через жопу, храня списки чисел везде.

Как будет выглядеть алгоритм?

> Специально для вас - решение попроще:

Вы бы еще однострочник вставили со всеми возможными трюками.
Простота решения - не то же самое, что краткость программы. Это решение еще хуже предыдущего. Тут не соревнование по codegolf.

> поскольку недоучки, узнавшие новый термин, но не смыслящие в вопросе, меня огорчают.

Очень высокомерное заявление. Вы сюда только чтобы самоутвердиться заходите? В противном случае, зря вы тут пишете. Пользы от ваших ответов вопрошающим - нет. Если задающий вопрос про динамическое программирование ничего про него не знает, то понять ваше решение не имеет вообще никаких шансов. Даже человек, знающий ДП не факт что поймет, какие у вас состояния. А главное - почему оно работает (если оно вообще работает).

> Заходите ко мне почаще, меня забавляют задорные идиоты собеседники.

От "собеседника" и слышу.

Как будет выглядеть алгоритм?

Ваше решение не работает, хотя бы потому, что во входном массиве могут быть отрицательные числа. И когда их берет человек, у вас считается, что это положительную карточку взял робот. Кроме того считать "сумма у человека минус сумма у робота" - тоже неправильно. Вообще, похоже, что вы специально писали решение так, чтобы в нем было как можно сложнее разобраться.

Можно было бы хотя бы пару слов сказать, что это Динамическое Программирование.

Как отсортировать двусвязный список SplDoublyLinkedList?

Руслан ., Когда вы сортировку слияния делаете, вы же после рекурсивных вызовов делаете еще и слияние за O(n). Все, что добавляется теперь - еще одно O(n), которое, кстати, все-равно нужно, если структура данных не поддерживает актуальное количество элементов, доступное за константу (надо же подсчитать количесво элементов и найти середину).

Не важно сколько и чего вы добавите в функцию, покуда она делает O(n) операций, не считая рекурсивных вызовов, суммарная сложность будет O(n log n) по основной теореме.

> Кроме этого было требование сортировать на месте

Это же списки! Тут не надо выделять дополнительную память. Ну если вам так хочется, то пишите quicksort.

> quicksort заточен на работу с индексами

Квиксорту не нужен случайный досуп! Посмотрте на код из вики, например. Там тупо делается проход по массиву с конца. Индексы i и j всегда сдвигаются только на один соседний элемент и начинаются с начала или конца куска массива. Тут все отлично работает на списках. Если вы в функцию передадите 2 крайних элемента со ссылками вперед/назад, то все будет работать. Другое дело, что этот пхп-шный список похоже и это не поддерживает.

Т.е. лучше, конечно, использовать другую структуру данных. Или нормальный список или массив. Но если надо использовать этот спискок - то это тоже возможно и даже не сложно по коду.

Как отсортировать двусвязный список SplDoublyLinkedList?

Нет, с точки зрения реализации - это проще, чем писать свой список. Но выглядит противно, да.

Как отсортировать двусвязный список SplDoublyLinkedList?

Руслан ., вы не правы. Не нужно случайного доступа, чтобы отсортировать за n log n. Та же сортировка слиянием делается так: проходим по списку один раз, чтобы значть его длину и найти середину. Разбиваем на 2 списка, сортируем каждый рекурсивно и потом сливаем два получившихся списка.

А еще можно quicksort сделать похоже - там не надо никакого случайного достпа - нужно 2 указателя, которые идут по списку с начала и с конца.

Обрезка невыпуклого полигона. Как определить множество полигонов на выходе?

Ага, так понятнее, что там за алгоритм.

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

Как реализовать алгоритм комбинаторики в программе?

> Но что делать с лишним числом,

Ничего не делать. Просто у вас 19 мест, чтобы числа вставить и 20 чисел. В последнем, 19 уровне рекурсии, если вы до него дошли, у вас в списке свободных чисел будет 1 число. Надо только условие оставновки поменять с "плставили 20 чисел" до "заполнили 19 мест".

Насколько трудное данное тестовое задание и что полистать чтобы его решить?

Обход в ширину находит кратчайший путь только если все ребра длины 1. Однако, в этой задаче ребра расстояния между звездами разные.

PS. Можно обобщить алгоритм BFS на случай целых длин ребер от 0 до некоторого небольшого K, но вряд ли вы имели это ввиду, потому что оно не совсем тривиально.

Как уравнять графы?

artshelom, Вряд ли есть библиотека для этого - обход такой является весьма тривиальным алгоритмом, а задача довольно спецефическая. Любая библиотека, достаточно гобкая чтобы эту конкретную задачу решить, потребует столько вызывающего кода и настроек, что с нуля написать будет быстрее, проще и короче.

>И есть ещё кое-что, это если к одной вершине есть несколько ребер между которыми нету уравновешивания, то получается придется делать несколько обходов. А это боюсь сведется к бесконечности

Не надо делать несколько обходов. Если уровновесить не получается, то это станет заметно на первом же конфликтущем ребре.

Набросок кода на С++, на C# перепишите сами:

// vector<vector<pair<int, int>> edges - ребра. edges[i][j] j-ое ребро из вершины i. first - конец ребра, second - длина ребра.
// heights - массив для ответа.
// was - массив для пометок о пройденных вершинах
bool Dfs(int v, int height, const vector<vector<pair<int, int>> &edges, int heights[], bool was[]) {
  was[v] = true;
  heights[v] = height;
  for (const auto &edge : edges[v]) {
     int end = edge.first;
     int expected_height = height + edge.second;
     if (was[end]) {
       // Конец уже обработан. Проверить на конфликт в этом ребре.
       if (heights[end] != expected_height)
         return false;
    } else {
      // Конец не обработан, обрабатываем
      if (!Dfs(end, expected_height, edges, heights, was))
        return false;
    }
  }
  return true;
}

...
// как вызывать dfs

was[] <- заполнить false для всех вершин
bool good = true;
for (i = 0; i < n; ++i) {
  // вершина была обработана предыдущим обходом.
  if (was[i])
    continue;
  if (!Dfs(i, 0, edges, heights, was)) {
    good = false;
    break;
  }
}

// тут heights[] уже заполнен правильно, если good == true, иначе - в графе неустранимый конфликт.

Можно все массивы сделать глобальными, а не передавать аргументами функции. edges может быть массивом списков структур {конец, длина} или двумя отдельными двумерныим массивами.

Алгоритм для поиска самого длинного пути в орентированом графе?

longclaps, Автор уточнил в комментарии под вопросом:
"ff0xff ff0xff Автор вопроса
Да, граф ацикличен, нет бесконечный путь получать нельзя. "

Как найти наименьший квадрат из фигур тетрамино?

longclaps, Он лучше тем, что там вариантов на каждом уровне в несколько раз меньше. Так же, в вашем варианте несколько разных путей приведут к одному и тому же варианту заполнения поля. В полном переборе это все очень сильно замедляет его.

Алгоритм для поиска самого длинного пути в орентированом графе?

longclaps, Да не надо ничего удалять. Мы в поиске в глубину уже к пройденному ребру никогда не придем в ациклическом графе. Никак, про него можно забыть, оно где-то сзади может быть в пути и учитывается только в верхних уровнях рекурсии.

Еще раз, функция от вершины возвращает самый длинный путь, начинающийся в ней. Что делает? Смотрит все исходящие ребра и вызвает себя от вершин детей. Поскольку граф ациклический, все пути из этих детей вершин никогда не вернутся в начальную вершину. Можно представить, что ребра к этим вершинам проста удалены из графа и это не изменит ответ никак.

Представте себе дерево подвешенное. В произвольном ациклическом графе чуть-чуть сложнее, но все тоже самое.

Как составить список пути используя алгоритм BFS?

carabia, я бы сделал 2 2D массива prev_row и prev_col. Заполнял бы их при помещении вершины в очередь.

При восстановлении вывести текущие x и y, потом перезаписать их (не забыть использовать временную переменную, чтобы не брать новое значение x и старое значение y как индексы для получения нового y).

Хотя это не сильно-то оптимальнее.

Еще, комментарий - вы выводете путь в обратном порядке. Надо заполнять массив с конца вместо вывода.

Как найти наименьший квадрат из фигур тетрамино?

longclaps, в тетрамино 4 клетки. Любая одна из них должна покрыть текущую клетку. Вот и 4 варианта. Вариант, что текущая клетка не покрыта рассматривается отдельно.

Алгоритм для поиска самого длинного пути в орентированом графе?

longclaps, Граф ациклический. Т.е. в нем нет циклов. Значит, все ребра в длиннейшем, да и любом, пути с вершины не могут быть в пути, который нас в нее привел.

Как реализовать алгорим задачи о сумме подмножеств?

Очевидно, что в задаче ограничения на сами числа небольшие (хоть автор и не указал). Иначе задача не имеет решения, которое можно выполнить до тепловой смерти вселенной.

Алгоритм для поиска самого длинного пути в орентированом графе?

В ациклическом ориентированном графе, самое простое - это DFS. Рекурсивная функция, которая возвращает самый длинный путь с заданной вершины. С запоминантем ответа - если уже запускались с этой вершины, возвращаем уже подсчитанный результат. Иначе перебираем все ребра из этой вершины и берем максимум из dfs от конца ребра + длига ребра. Запоминаем этот максимум и возвращаем результат.