Optimizing SPOJ edit distance solution
I've solved that problem in java and c++ (2nd and 3th places in best solutions category :) so I can compare the local and the remote execution time in order to see - how much faster should be your solution in order to pass.

So, the local execution time of my java solution is 78 ms for the such testcase (10 pairs x 2000 chars), the robot's time is 500 ms, so my PC is ~6.5 times faster. Then the following python DP solution takes 3.6 seconds on my PC so, it would take ~23.5 seconds on the remote PC. So if the remote time limit 15 seconds, the following solution must be minimum ~ 1.56 times faster in order to pass. Ufff.... 

import time

try:
    # just to see the Python 2.5 + psyco speed - 17 times faster than Python 2.7 !!!
    import psyco
    psyco.full()
except:
    pass

def editDistance(s1, s2):
    if s1 == s2: return 0 
    if not len(s1):
       return len(s2)
    if not len(s2):
       return len(s1)
    if len(s1) &gt; len(s2):
        s1, s2 = s2, s1
    r1 = range(len(s2) + 1)
    r2 = [0] * len(r1)
    i = 0
    for c1 in s1:
        r2[0] = i + 1
        j = 0
        for c2 in s2:
            if c1 == c2:
                r2[j+1] = r1[j]
            else:
                a1 = r2[j]
                a2 = r1[j]
                a3 = r1[j+1]
                if a1 &gt; a2:
                    if a2 &gt; a3:
                        r2[j+1] = 1 + a3
                    else:
                        r2[j+1] = 1 + a2
                else:
                    if a1 &gt; a3:
                        r2[j+1] = 1 + a3
                    else:
                        r2[j+1] = 1 + a1
            j += 1
        aux = r1; r1 = r2; r2 = aux
        i += 1
    return r1[-1] 

if __name__ == "__main__": 
    st = time.time()
    t = raw_input()  
    for i in range(int(t)):    
        a, b = raw_input(), raw_input()
        print editDistance(a, b)
    #print "Time (s): ", time.time()-st


What I can say - It's very very hard or may be impossible to pass that puzzle using Python and DP approach (using java or c++ - peace of cake). Wait, wait - ask you - what about that two guys that passed using python? Ok, the answer is easy - they use something different. What's exactly? Something that I've used for java solution I think. That stuff just blows away the competitors....