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

[setare]

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

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

[setare]

Хорошо!! Просто, понимаете, как сформулировал мне задачу преподаватель, так я и пишу ее здесь. Есть строка, состоящая из цифр, например 1234, которую вводит пользователь. Между цифрами есть пустоты (пробелы). Нужно поссчитать сколькими способами можно расставить мины в нижней строчке! Строчка находится прямо под этой строкой. Мины можно ставить как под цифрой, так и нет.
например:
+-мины,*-пустоты

1 2 * * * 3 * * 1
++ +   +++	+
  + + +   ++ ++

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