[[AlgorithmQuiz/3Plus1]]을 [[DynamicProgramming]]으로... --[[windist]]

캐쉬에 저장하고, 이미 계산한 값에 대해서는 캐쉬의 값을 이용. [[yong27]]의 코드보다 훨씬 빠르게 동작한다고함.

{{{#!python
cache = dict()
def getCycleLength(i):
    if i == 1:
        cnt = 1
    elif cache.has_key(i):
        cnt = cache[i]
    else:
        if i % 2:
            j = i * 3 + 1
        else:
            j = i / 2
        cnt = getCycleLength(j) + 1
    cache[i] = cnt
    return cnt

def getMaxCycleLength(i, j):
    cyclelist = list()
    for k in range(i, j + 1):
        cyclelist.append(getCycleLength(k))
    print i,j, max(cyclelist)
    return max(cyclelist)

def main():
    i,j = map(int,raw_input().split())
    print i, j, getMaxCycleLength(i,j)

if __name__=='__main__':
    import time
    pre = time.time()
    print getMaxCycleLength(1,100000)
    post = time.time()
    print post - pre
}}}