SPOJ - Alphacode, using dynamic programming
First of all, I would simplify the driver loop in main(), like this:

int main() {
    std::string msg;                                                                      
    while ((std::cin &gt;&gt; msg) &amp;&amp; (msg != "0")) {                                           
        std::cout &lt;&lt; decodings(msg) &lt;&lt; '\n';                                              
    }                                                                                     
}


Observations:


The status of the &gt;&gt; operator is checked, so that an input error or EOF would cause the program to end.
a was a cryptic variable name.
There is no point in saving all of the input first.  Each message is an independent test case.  You can start computing the result for each line as you encounter it.  That potentially saves you some delay.  It also eliminates the input global variable.  Most importantly, it helps declutter the dp() function, which only cared about input[i] anyway.
dp(i) was a cryptic and unhelpful function name.  It's not obvious what it stood for, and even if you knew that it meant "dynamic programming", it didnt't say anything about what it computes.


Your algorithm seems very complicated.  It seems to use a 2D table of strings (which is like a 3D table of chars) for memoization.  There are no comments, so I couldn't figure out what you were trying to do.  I decided it would be easier to write a solution from scratch.

Suggested solution

#include &lt;cassert&gt;
#include &lt;cstdint&gt;
#include &lt;iostream&gt;
#include &lt;string&gt;

/**
 * Checks whether the character 'a' could represent a letter (1 to 9).
 */
bool isletter(char a) {
    return '1' &lt;= a &amp;&amp; a &lt;= '9';
}

/**
 * Checks whether the string "ab" could represent a letter (10 to 26).
 */
bool isletter(char a, char b) {
    return (a == '1' &amp;&amp; ('0' &lt;= b &amp;&amp; b &lt;= '9')) ||
           (a == '2' &amp;&amp; ('0' &lt;= b &amp;&amp; b &lt;= '6'));
}

/**
 * Counts the number of ways the message could be decoded.
 */
std::int64_t decodings(const std::string&amp; msg) {
    std::string::size_type len = msg.length();
    if (len == 0) return 1;

    std::int64_t prev_count = 1,
                 curr_count = isletter(msg[0]);
    for (int i = 1; i &lt; len; ++i) {
        // Try decoding the last two characters as a letter, and
        // try decoding the final character as a letter.
        std::int64_t new_count = prev_count * isletter(msg[i - 1], msg[i]) +
                                 curr_count * isletter(msg[i]);
        prev_count = curr_count;
        curr_count = new_count;
    }

    return curr_count;
}

int main() {
    assert(decodings("25114") == 6);
    assert(decodings("1111111111") == 89);
    assert(decodings("3333333333") == 1);

    std::string msg;
    while ((std::cin &gt;&gt; msg) &amp;&amp; (msg != "0")) {
        std::cout &lt;&lt; decodings(msg) &lt;&lt; '\n';
    }
}


Observations:


decodings() is obviously O(L) in time and O(1) in space, so it's hard to beat.
I've used std::int64_t, since that is what the challenge specifies.
For good measure, I've added assertions for the three provided test cases.