Ресурсы динамического программирования в C?

Я буду писать онлайн-тест Google завтра как свежее. По-видимому, они определенно задают одну проблему в динамическом программировании?Ресурсы динамического программирования в C?

Кто-нибудь знает о хорошем ресурсе для сбора проблем DP в C вместе с решениями? Я знаю, что DP & использовал его по случаю или дважды. Тем не менее, я чувствую, что проблема с DP-проблемой в тестировании, предыдущая практика типичных проблем упростит подход.

Любые хорошие ресурсы или комплекты проблем с решениями на C будут высоко оценены. Благодарю.

источник

2011-01-09 EsotericMe

Вы отметили эту проблему тегом Java - будут ли ресурсы Java также в порядке? – templatetypedef

Несомненно, может быть, я получу несколько идей реализации. Я предположил, что, возможно, люди из Java могли бы в какой-то момент мигрировать из C: P – EsotericMe

У меня есть несколько примеров на C++; это будет хорошо? – templatetypedef

Хорошо, поэтому я действительно надеюсь, что это не считается «бесстыдной саморекламой», поскольку все эти ссылки относятся ко всем фрагментам кода, которые я опубликовал на своем личном сайте. Если это неуместно, сообщите мне об этом, и я могу их снять.

Вот несколько забавных проблем DP, которые в значительной степени классика:

Минимальное расстояние редактирования: Даны две строки А и В, найти кратчайшее количество правок (вставки, делеции или замены), необходимые для преобразуем А в В. Это называется расстоянием Левенштейна. (My solution)
Оптимальное выравнивание последовательностей: если заданы две строки A и B, найдите минимальное количество промежутков, которые необходимо вставить в последовательность для выравнивания A и B. Это называется алгоритмом Needleman-Wunsch. (My solution)
Кратчайшие пути с одним источником: заданный ориентированный граф G и один узел s, найдите длины кратчайших путей от s друг к другу в графе, предполагая, что ребра могут быть положительными или отрицательными, но не существует циклов , Это алгоритм Беллмана-Форда. (My solution)
Все парные кратчайшие пути: заданный направленный граф G, найдите минимальные расстояния между всеми парами узлов. Это алгоритм Флойда-Варшалла. (My solution)

Надеюсь, это будет полезно, и удачи на завтра!

источник

2011-01-09 08:38:27 templatetypedef

Прокомментированный код. +1. –

Спасибо тонну. Это может многое помочь. Если вы знаете больше таких проблем, пожалуйста, дайте мне знать. – EsotericMe

Project Euler: http://projecteuler.net/ –

Сайт Topcoder изумительный. Не все проблемы используют DP, но многие это делают. Свободный полный доступ ко всем проблемам прошлых соревнований, которые находятся на 3 разных уровнях сложности, а также после матча объяснения каждой проблемы от автора проблемы. Не только это, но вы можете быстро выкопать исходный код, представленный любым кодером в конкурсе.

Не возвращайтесь туда некоторое время, но они позволяют, по крайней мере, C++, Java, C#, и теперь я считаю несколько других языков.

источник

2011-01-09 09:28:10

Я предлагаю u, собрать книгу «Введение в алгоритмы биоинформатики». У этого есть глава полностью о DP.As @templatetypedef упоминается Минимальное расстояние редактирования, Оптимальное выравнивание последовательности имеет и другие проблемы с ними. Хотя нет реализации в нем. Вы должны сделать это самостоятельно. Но вы найдете довольно интересное их чтение.

источник

2011-01-09 10:37:42 saiful103a

На практике вы можете воспользоваться одной из доступных проблем в SPOJ. Чтобы распознать DP легко, вы можете проверить на Problems Classifier (ключевое слово: dp).

источник

2011-01-09 12:22:14 kuszi

Ресурсы динамического программирования в C?

ответ

Смежные вопросы