Шифрование текста

[ДмитрийПО]

Помогите найти решение к этой задаче(желательно код):
В сообщении, состоящем из одних русских букв и пробелов, каждую букву заменили ее порядковым номером в русском алфавите (А - 1, Б - 2, ..., Я - 33), а символ пробел - нулем. Требуется написать программу, которая по заданной последовательности цифр (не более 100) находит количество исходных сообщений, из которых она могла бы получиться.
Очень надеюсь на вашу помощь!

[BDA]

Зачем искать, время терять? Быстрее же написать его
В простейшем случае понадобится 3 глобальных переменных (для строки, для длины строки, для счетчика исходных сообщений) и немного знаний о рекурсии. Имея строку и текущий индекс в ней (сначала равный единице), "откусываем" 1 символ, а если возможно, то два. После чего опять вызываем ту же функцию, но с новым индексом, продвигаясь по строке (вызов осуществляется и после 1, и после 2 "откусанных" символов). Если строка кончилась, то увеличиваем глобальный счетчик. В конце работы программы печатаем глобальный счетчик.

Ждем Ваших наработок.

[Serge_Bliznykov]

задача олимпиадная.
Рекурсивное решение для больших строк получается чрезвычайно неэффективное и затратное (как по требованиям к размеру стека, так и требования к времени вычислений). Если это нужно для сдачи решения в онлайн систему проверки, то решение с рекурсией НЕ ПРОКАТИТ!!!

Решать задачу нужно с помощью динамического программирования.
Как написано уважаемым LeBron тут - Delphi.Динамическое программирование
но, кода решения там нет!! Там только описание подхода к решению задачи!


ну и вдогонку.
Если кому-то интересно неэффективное решение через рекурсию (upd. по алгоритму описанному чуть выше), то вот оно:

var
  cnt : LongInt;
  LenS : byte;
  s : string;

procedure CountVariation(const Indx : byte);
begin
  if Indx>LenS then Inc(cnt)
  else begin
    if s[Indx] in ['0'..'9'] then begin  CountVariation( Indx+1 ); end;
    if Indx<LenS then begin
      if ((s[Indx] in ['1'..'2']) and (s[Indx+1] in ['0'..'9']))
           or (s[Indx] = '3') and (s[Indx+1] in ['0'..'3'])  then
           begin  CountVariation(Indx+2); end;
    end;
  end;
end;

begin
  s := '1025';
  cnt := 0;
  LenS := Length(s);
  CountVariation( 1 );
  WriteLn('Count of messages: ', cnt);
  Readln;  
end.

[BDA]

Serge_Bliznykov, спасибо, нужно будет в свободное время уделить больше внимания динамическому программированию.