SPOJ Emoticon challenge
int dp(string s,int in,int len,int pos){



Where are the comments to explain the meanings of the variables? We're forced to reverse engineer them.


    if(in == len){
        return 0;
    }
    if(pos == 0){
        if(s[in] == 'K'){
            return dp(s,in+1,len,1)+dp(s,in+1,len,0);
        }
        return dp(s,in+1,len,0);
    }
    if(pos == 1){
        if(s[in] == 'E'){
            return dp(s,in+1,len,2)+dp(s,in+1,len,1);
        }
        return dp(s,in+1,len,1);
    }
    if(pos == 2){
        if(s[in] == 'K'){
            return 1+dp(s,in+1,len,2);
        }
        return dp(s,in+1,len,2);
    }
}



This is not dynamic programming. A dynamic programming approach to this problem must work on the following basis:


  Given a structure S which summarises the prefix str, and the next character ch, we need to derive a structure S' which summarises the prefix str + ch.


We have some easy conclusions:


S must provide us with the number of the desired subsequences, because at the end of the DP run we will only have S corresponding to the entire string. So it has a field which we can call kek.
If ch is neither 'E' nor 'K' then S' = S.
If ch != 'K' then S'.kek = S.kek.
If ch == 'K', S must provide us with some way of knowing how much bigger S'.kek should be than S.kek. Obviously that must be the number of KEK subsequences ending with ch, which is the number of KE subsequences in str.


You should be able to carry this reasoning through to fill out the entire list of fields required in S and the logic to update them when reading an 'E' and when reading a 'K'.