Мины, Динамическое программирование Опции

[setare]

Здравствуйте! Нам дали задачу на динамическое программирование толком не обьяснив как можно эту тему использовать в решении задач. Мне дали следующую задачу:
Есть строка, которую вводит пользователь, например: 1 2***3*1 После этого надо написать программу, которая бы сосчитала сколькими способами можно поставить мины, как в игре сапере под каждой цифрой. Как можно подойти к этой задаче? И как рассчитать эти способы? А также массив будет двумерный или одномерный только для самых мин? Спасибо за ответ! И я пользовалась поиском, но по-моему такой темы у вас не была. По крайней мере я ничего не нашла.

Сообщение отредактировано: setare - 12.12.2005 23:52

[setare]

Malice, спасибо за программу, но мне кажется, что она написана не в динамическом программировании! Но все равно спасибо!
Я еще раз привожу пример:
Не обращайте внимание на пробелы, которые я сейчас поставлю. Проблеами здесь являются именно минусики. Я поставлю пробелы только для наглядности. Эти звездочки не попадают прямо под минусики, но я больше не знаю ка это изобразить!Надеюсь сейчас хотя бы это как-то понятно!

- 1 2 - - - 3 - - 1 -
* * * * ** *
* ** ** * *

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

Да, число плюсов точно равно цифрам, и хочу обратить ваше внимание на то, что в примере это именно так!
Да, пробелы могут стоять и впереди и после первой и последней цифры соответсвенно!
Под пробелами не имеет смысла от каких цифр стоит мина. там может быть мина, например, как от 2 так и от 1. Самое главное, чтобы число соответсвовало цифрам. Напримар если стоит 1 пробел пробел 2, то должно стоять в общем только 3 мины рядом с 1 и 2. Значит, может стоять мина под 1 пробелом и проблом, потом пробелом пробелом 2, пробелом 2 иесли там дальше есть пробел или число, то и дальше мина.
Препода я больше не могу найти, его не бывает в университете в течение недели! Плюс он другому человеку дал это же задание и обьяснил его так же как и мне и больше ничего не сказал. Этот другой человек, если вы скажете, чтобы я обратилась к нему за вопросами, сам ничего не смыслит в программировании и в этих задачах!