SPOJ 394- ACODE

Problem Statement

As from the problem-tag, you can see this is a DP( Dynamic Programming ) problem. Don't know Dynamic Programming? Here are some articles: Codechef, TopCoder. Try to solve a sample problem, for example, Fibonacci Numbers.

Let's start cracking the problem. To solve a DP problem, the hardest and important part is to find the relation between previous or next steps and current step. We need to find out how the solution of the current step depends on its previous steps or next steps.

Looking at:      2 5 1 1 4
       from left to right

• Step 1: You can only interpret this as 2(B). Decoding- BEAAD  So, DP[1] = 1
• Step 2: This can be 5(E) or collaborating with 2, it can be 25(Y). Result is BEAAD + YAAD. So, DP[2] = 2
• Step 3: Can only be interpreted as 1(A). 51 is not valid, as stated in problem. BEAAD + YAAD. DP[3] = 2. 
• Step 4: Will be interpreted as 1(A). BEAAD + YAAD+...  Look at the decodings, if we interpret as 1(A) the decodings are same as the step 2, right? There's not a single change. But if interpreted as 11(K) , we are using the step 3's digit also, meaning we cannot use step 3's solution for 11(K) as we are already using that digit in current step. So where do we go?= Step 2. We aren't using that digit (5). So we replace '1' '1' with '11' in step 2's solution. ...+ BEKD + YKD. Finally DP[4] = 4
• Step 5: Interpret as 4(D) - decodings are: BEAAD + YAAD + BEKD + YKD. Interpret as 14(N), decodings are from step 3. BEAN + YAN. Add them up, DP[5] = 6

If you understood the above process, you can code it in. Now, this is the basic understanding of the problem, there are few special test cases that you'll have to check.
If you did not understand, try solving some simpler DP problems. Here's one- COINS

 Sample Code:

#include<stdio.h>
#include<map>
#include<string.h>
using namespace std;
char a[5002];
map<int,long long >dp;
int f=1;

long long acode(int n)
{
    int temp= (a[n-1]-48)*10+(a[n]-48);
    if(n==0) return 1;
    if(n==-1) return 1;
    if(dp[n]!=0) return dp[n];    //memorization

    dp[n] = acode(n-1);
    if(a[n+1]!= '0'&&a[n]!='0')
    {
        if(temp>9&&temp<27)
        {
            dp[n]= acode(n-1) +acode(n-2);
        }
    }
    else if(a[n+1]== '0'&&a[n]=='0') {
        f=0;
    }

    if (f==1) return dp[n];
    else return 0;
}

int main()
{
    char x[]={'0','\0'};
    while(scanf("%s",&a))
    {
        if( !strcmp(a,x) ) break;
        int i,l=strlen(a);
        dp.clear();
        f=1;
        printf("%lld\n",acode(l-1));
    }
}


* Let me know if you got any question or the post contains any wrong information